1228C.md (1685B)
1 Source: https://codeforces.com/problemset/problem/1228/C 2 3 C. Primes and Multiplication 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 Let's introduce some definitions that will be needed later. 22 23 Let $prime(x)$ be the set of prime divisors of $x$. For example, $prime(140) = \{ 2, 5, 7 \}$, $prime(169) = \{ 13 \}$. 24 25 Let $g(x, p)$ be the maximum possible integer $p^k$ where $k$ is an integer such that $x$ is divisible by $p^k$. For example: 26 27 * $g(45, 3) = 9$ ($45$ is divisible by $3^2=9$ but not divisible by $3^3=27$), 28 * $g(63, 7) = 7$ ($63$ is divisible by $7^1=7$ but not divisible by $7^2=49$). 29 30 Let $f(x, y)$ be the product of $g(y, p)$ for all $p$ in $prime(x)$. For example: 31 32 * $f(30, 70) = g(70, 2) \cdot g(70, 3) \cdot g(70, 5) = 2^1 \cdot 3^0 \cdot 5^1 = 10$, 33 * $f(525, 63) = g(63, 3) \cdot g(63, 5) \cdot g(63, 7) = 3^2 \cdot 5^0 \cdot 7^1 = 63$. 34 35 You have integers $x$ and $n$. Calculate $f(x, 1) \cdot f(x, 2) \cdot \ldots \cdot f(x, n) \bmod{(10^{9} + 7)}$. 36 37 Input 38 39 The only line contains integers $x$ and $n$ ($2 \le x \le 10^{9}$, $1 \le n \le 10^{18}$) — the numbers used in formula. 40 41 Output 42 43 Print the answer. 44 45 Examples 46 47 Input 48 49 ``` 50 10 2 51 ``` 52 53 Output 54 55 ``` 56 2 57 ``` 58 59 Input 60 61 ``` 62 20190929 1605 63 ``` 64 65 Output 66 67 ``` 68 363165664 69 ``` 70 71 Input 72 73 ``` 74 947 987654321987654321 75 ``` 76 77 Output 78 79 ``` 80 593574252 81 ``` 82 83 Note 84 85 In the first example, $f(10, 1) = g(1, 2) \cdot g(1, 5) = 1$, $f(10, 2) = g(2, 2) \cdot g(2, 5) = 2$. 86 87 In the second example, actual value of formula is approximately $1.597 \cdot 10^{171}$. Make sure you print the answer modulo $(10^{9} + 7)$. 88 89 In the third example, be careful about overflow issue.