Primes and Multiplication Codeforces1228C 2019-10-01 算法竞赛 暂无评论 64 次阅读 题目链接：[https://codeforces.com/contest/1228/problem/C](https://codeforces.com/contest/1228/problem/C)  ## 思路 1. prime( x ) : x 的质因数 2. g (x,p) : x的能被p整除的最大因数（如果p为质数可以理解为x质因数分解后p出现的次数 ） 3. f (x,k)= g (k, prime(x) ) 4. f(x,1) \* f(x,2) \* f(x,3) \* ... f(x,n) = g(1, prime(x) ) \* g(2, prime(x) ) \* g(3, prime(x) ) \* ... g(n,prime(x) ); 5. 上式 = g( n!, prime(x) )，于是可以参考 n! 的质因数分解方法 : (1). 先求出x 的质因数,即 prime(x) = p1,p2,...pk (2). 对每个质因数$p_{i}$ g (n! , $p_{i}$) = $pi^{m}$ 其中 m = $\lfloor\frac{n}{pi}\rfloor$+$\lfloor\frac{n}{pi^2}\rfloor$+$\lfloor\frac{n}{pi^3}\rfloor$+... (3). 程序中 $m_{i}$ = get(n,$p_{i}$) 最后答案 ans = $p_{1}^{m_{1}}$ \* $p_{2}^{m_{2}}$ \* $p_{3}^{m_{3}}$ \* ... \* $p_{k}^{m_{k}}$ （% mod） ## 代码 ```javascript #include <iostream> #include <vector> using namespace std; typedef long long LL; const LL MOD = 1e9 + 7; int x; LL n; LL mpow(LL x, LL n) { LL res = 1; while (n > 0) { if (n & 1) res = (res * x) % MOD; x = (x * x) % MOD; n >>= 1; } return res; } LL get(LL n, LL p) { LL s = 0; while (n) s += n / p, n /= p; return s; } int main() { scanf("%d%lld", &x, &n); vector<int> v; for (int i = 2; i * i <= x; i++) { if (x % i == 0) { while (x % i == 0) { x /= i; } v.push_back(i); } } if (x > 1) { v.push_back(x); } LL ans = 1; for (int i = 0; i < v.size(); i++) { ans = (ans * mpow((LL) v[i], get(n, (LL) v[i]) ) ) % MOD; } printf("%lld\n", ans); } ``` 标签: 算法 本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。
评论已关闭