POJ 1845 Sumdiv （数论，约数和）

POJ 1845 Sumdiv （数论，约数和）

Description

Consider two natural numbers A and B. Let S be the sum of all natural divisors of A^B. Determine S modulo 9901 (the rest of the division of S by 9901).

Input

The only line contains the two natural numbers A and B, (0 <= A,B <= 50000000)separated by blanks.

Output

The only line of the output will contain S modulo 9901.

Sample Input

2 3

Sample Output

15

题意

给出两个数a,b，求a^b的所有的因子之和。

思路

对于任意一个数a，我们都可以将他表示为 a=Pm11∗Pm22∗...∗Pmnn

此时，对于数a，它的因子个数共有 (m1+1)∗(m2+1)∗...∗(mn+1)

所有因子和为 (P01+P11+...+Pm11)∗(P02+P12+...+Pm22)∗...∗(P0n+P1n+...+Pmnn)

于是，我们可以对a进行素因子分解，然后利用公式，求得所有因子和。

且 ab=Pm1∗b1∗Pm2∗b2∗...∗Pmn∗bn

无奈这道题当时打算用乘法逆元计算等比数列前n项和的时候一直WA，于是只能改用递归咯！

AC代码

#include#include#include#include#includeusing namespace std;#define mod 9901typedef unsigned long long LL;LL mult(LL a,LL n){ LL ans=1; while(n) { if(n&1)ans=(a*ans)%mod; a=(a*a)%mod; n>>=1; } return ans;}/* 乘法逆元求解等比数列前n项和：status WALL solve(int a,int b){ return ((mult(a,b+1)-1)*mult(a-1,9901-2))%mod;}*/LL sum(LL p,LL n) //等比求和{ if(n==0)return 1; if(n&1)return ( (1+mult(p,n/2+1)) * sum(p,n/2) ) % mod; return ((1+mult(p,n/2+1)) * sum(p,n/2-1) + mult(p,n/2) )% mod;}void numberfixed(LL n,LL m){ LL s=1; for(LL i=2; i*i<=n; i++) if(n%i==0) { int b=0; while(n%i==0) { b++; n/=i; } s=(s*sum(i,b*m))%mod; } if(n!=1) s=(s*sum(n,m))%mod; printf("%I64d\n",s);}int main(){ LL a,b; while(~scanf("%I64d%I64d",&a,&b)) { if(a==0)printf("0\n"); else numberfixed(a,b); } return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。