本文共 1442 字，大约阅读时间需要 4 分钟。
A^B 能够写成 p1^e1 * p2^e2 * .....*pk^ek。(A。B <= 1000000)
求 ∏1^3+2^3+...+(ei+1)^3 % 10007的值。
依据质因子分解定理知A = p1^a1 * p2^a2 *.....* pk^ak，那么A^B = p1^(a1*B) * p2^(a2*B) *.....*pk^(ak*B)。
那么ei = ai*B，带入上式计算。
#include #include #include #include #include #include #include #include #include #include #include #include #include #include //#define LL __int64#define LL long long#define eps 1e-9const double PI = acos(-1.0);using namespace std;const int maxn = 1000010;const int mod = 10007;LL A,B;int prime[maxn];bool flag[maxn];LL facCnt[1010]; //由于数组开的太大，每次都须要初始化，导致TLE了几次。int cnt;void getPrime(){ memset(flag,false,sizeof(flag)); prime[0] = 0; for(int i = 2; i < maxn; i++) { if(flag[i] == false) prime[++prime[0]] = i; for(int j = 1; j <= prime[0] && prime[j]*i < maxn; j++) { flag[prime[j]*i] = true; if(i % prime[j] == 0) break; } }}void getFac(){ LL tmp = A; cnt = 0; memset(facCnt,0,sizeof(facCnt)); for(int i = 1; i <= prime[0]&&prime[i]*prime[i] <= tmp; i++) { if(tmp % prime[i] == 0) { while(tmp%prime[i]==0) { facCnt[cnt]++; tmp /= prime[i]; } cnt++; } if(tmp == 1) break; } if(tmp > 1) { facCnt[cnt++] = 1; }}int main(){ getPrime(); int item = 0; while(~scanf("%I64d %I64d",&A,&B)) { getFac(); LL ans = 1; for(int i = 0; i < cnt; i++) { LL s = (((facCnt[i]*B+1)*(facCnt[i]*B+2))/2 )%mod; s = (s*s)%mod; ans = (ans*s)%mod; } printf("Case %d: %I64d\n",++item,ans); }}
转载地址：http://lehux.baihongyu.com/