学步园

题意：求A^B的值的所有因子的和模9901，例如2^3=8  =>  1+2+4+8=15。最后答案为15%9901 = 15。

分析：先将A^B分解成素因数形式：A^B = (P1^k1) + (P2^k2) + (P3^k3) + ...

那么A^B所有因子之和就是：S = (1 + P1^1 + P1^2 + P1^3 +...+ P1^K) * (1 + P2^1 + P2^2 + P2^3+...+P2^K) * (1 + P3^1 + P3^2 + P3^3 +...+ P3^K) * (...

计算 1 + P + P^2 + P^3 +...+ P ^K 可用二分求解；

当k是偶数时：例如k=4，1 + P + P^2 + P^3 + P^4 = (1+P) + P^2 * (1+P*(1+P))；

当k是奇数时：例如k=5，1 + P + P^2 + P^3 + P^4 + P^5 = (1 + P + P^2) + P^3 * (1 + P + P^2)；

#include<iostream><br /> #include<cmath><br /> using namespace std;<br /> const int maxn = 10000;<br /> int A,B;<br /> int mod = 9901;<br /> __int64 pow(__int64 x,__int64 n)//求p^n<br /> {<br /> __int64 ret=1, s = x;<br /> while(1)<br /> {<br /> if(n & 1)<br /> ret = ((ret % mod) * (s % mod)) % mod;<br /> if(n >>= 1)<br /> s = ((s % mod) * (s % mod)) % mod;<br /> else break;<br /> }<br /> return ret;<br /> }<br /> __int64 sum(__int64 p, __int64 n)//求1 + p + p^2 +...+ p^n;<br /> {<br /> if(n==0)<br /> return 1;<br /> if(n & 1) //n % 2 == 0;<br /> return (((1 + pow(p,n/2+1)) % mod) * (sum(p,n/2) % mod)) % mod;<br /> else<br /> return (((1 + pow(p,n/2+1)) % mod) * (sum(p,(n-1)/2) % mod) + pow(p,n/2) % mod) % mod;<br /> }<br /> int main()<br /> {<br /> __int64 s, ans;<br /> int i, p[maxn], c[maxn]; //p[i]表示第i个素因子，c[i]表示它的个数。<br /> while(scanf("%d%d",&A,&B)!= EOF)<br /> {<br /> memset(p, 0, sizeof(p));<br /> memset(c, 0, sizeof(c));<br /> //a^b=p1^(c1*b) * .... * pi^(ci*b)<br /> //ans=(1+p1+p1^2+...+p1^(c1*b))*()...*(1+pi+pi^2+...+pi^(ci*b))<br /> //把A分解素数<br /> for(i=2; i*i<=A; i++)//求所有A的素因子存在p[]中，<br /> {<br /> if(A % i ==0)<br /> {<br /> p[++p[0]] = i;<br /> while( A % i == 0)<br /> {<br /> A /= i;<br /> ++c[p[0]]; //对应的素因子的个数。<br /> }<br /> }<br /> }<br /> if( A != 1) //处理最后一个数。<br /> {<br /> p[++p[0]] = A;<br /> c[p[0]] = 1;<br /> }<br /> ans = 1;<br /> for(i=1; i<=p[0]; i++)//sum=(p1^(n1*B+1)–1)/(p1-1)*(p2^(n2*B+1)–1)/(p2–2)*…<br /> {<br /> ans = ((ans % mod) * (sum(p[i], c[i]*B)) % mod) % mod;<br /> }<br /> printf("%I64d/n",ans);<br /> }<br /> return 0;<br /> }