首先我們將這個數化成唯一分解的形式， 也就是這樣x = p1^a1*p2^a2*...pn^an, 我們定義答案為f(x)，首先我們定義d(x)為x的約數的個數， 那么f(x) = x^(d(x)/2), 由費馬小定理m為素數a^(m-1) == 1 (mod m) => a^x = a^x%(m-1) (mod m) 其中m為素數，這樣我們就可以在計算中給冪函數的冪取摸了， 當a b互質的時候， d(ab) = d(a)*d(b) ?f(ab) = f(a)^d(b)*f(b)^d(a) f(pi^ai) = Pi^(ai+1)*ai/2..由這三個公式我們就可以計算x的約數之積了， 代碼如下：

#include <cstdio> #include <algorithm> #include <cstring>using namespace std; typedef long long LL; const LL MOD = 1000000007; int m; int numhash[200000+10], num; int getID(int t) {if(numhash[t] == -1)numhash[t] = num++;return numhash[t]; } LL prime[200000+10], primenum[200000+10];LL powmod(LL A, LL B) {LL res = 1;while(B){if(B&1)res = (res*A)%MOD;A = (A*A)%MOD;B >>= 1;}return res%MOD; }int main() {scanf("%d", &m);memset(numhash, -1, sizeof(numhash));memset(primenum, 0, sizeof(primenum));num = 0;for(int i=0; i<m; i++){int t;scanf("%d", &t);prime[getID(t)] = t;primenum[getID(t)]++;}LL ans = 1, d = 1;for(int i=0; i<num; i++){LL hh = prime[i];LL temp = powmod(hh, primenum[i]*(primenum[i]+1)/2);ans = powmod(ans, primenum[i]+1)*powmod(temp, d)%MOD;d = d*(primenum[i]+1)%(MOD-1);}printf("%I64d\n", ans);return 0; }

?

轉載于:https://www.cnblogs.com/xingxing1024/p/5117098.html

總結

以上是生活随笔為你收集整理的求解一个数的所有约数之积的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。