时间卡的真厉害,比赛五个小时都在优化
求出A的质因子A^B=(a0^p0*a1^pq*……*an^pn)^B=a0^(B*p0)*……*an^(B*pn)
aj^(B*pj)有B*pj+1个因子(aj^0,aj^1……aj^(B*pj)),因子aj^i的因子个数是i+1个;
(1^3+2^3+……(B*pj+1)^3)
所以M=(1^3+2^3+……(B*p0+1)^3)*(1^3+2^3+……(B*p1+1)^3)*……*(1^3+2^3+……(B*pn+1)^3)
n项立方和的公式n^2*(n+1)^2/4
#include<stdio.h> #include<string.h> #define inf 10007 int prim[200]; int f[1010]; int main() { int i,j,n,k,op=1,num; __int64 temp,flag,sum,A,B; memset(f,0,sizeof(f)); num=0; for(i=2;i<=40;i++) { if(f[i]==1)continue; for(j=i+i;j<1010;j+=i) { f[j]=1; } } for(i=2;i<1010;i++) { if(f[i]==0) prim[num++]=i; } while(scanf("%I64d%I64d",&A,&B)!=-1)//用int定义A,B就Wrong了 { B%=inf; printf("Case %d: ",op++); if(A==1){printf("1\n");continue;} n=A; k=0; temp=1; while(n>1&&k<num) { i=0; while(n%prim[k]==0) { i++;n/=prim[k]; } sum=((i*B+1)*(i*B+2)/2)%inf; sum=(sum*sum)%inf; temp=(temp*sum)%inf; k++; } if(n>1)//如果没找到质因子,质因子就是自身,有B+1个 { sum=((B+1)*(B+2)/2)%inf; sum=(sum*sum)%inf; temp=(temp*sum)%inf; } printf("%I64d\n",temp); } return 0; }