求解一个数的所有约数之积

首先我们将这个数化成唯一分解的形式， 也就是这样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

#include

#include

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

{

int t;

scanf("%d", &t);

prime[getID(t)] = t;

primenum[getID(t)]++;

}

LL ans = 1, d = 1;

for(int i=0; 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;

}