POJ 1845 Sumdiv

2019-11-08 03:08:17

字體：大中小

來源：轉載

供稿：網友

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 3Sample Output
15Hint
2^3 = 8. The natural divisors of 8 are: 1,2,4,8. Their sum is 15. 15 modulo 9901 is 15 (that should be output). Source
Romania OI 2002
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
逆元+等比數列求和~
因為num沒有清零檢查了兩個小時……果然總是用撤回是會出問題的……
（以上來自ACdreamer~）
#include<cstdio>#define modd 9901#define ll long longll x,b,num,ans,cnt,PRi[10001];bool bb[10001];ll cal(ll u,ll v,ll mod){	ll ret=0;u%=mod;	while(v)	{		if(v&1) ret=(ret+u)%mod;		u=(u+u)%mod;		v>>=1;	}	return ret;}ll mi(ll u,ll v,ll mod){	ll ret=1;u%=mod;	while(v)	{		if(v&1) ret=cal(ret,u,mod);		u=cal(u,u,mod);		v>>=1;	}	return ret;}int main(){	for(int i=2;i<=10000;i++)	{		if(!bb[i]) pri[++cnt]=i;		for(int j=1;pri[j]*i<=10000;j++)		{			bb[pri[j]*i]=1;			if(!(i%pri[j])) break;		}	}	scanf("%lld%lld",&x,&b);ans=1;	for(int i=1;pri[i]*pri[i]<=x;i++)	  if(!(x%pri[i]))	  {	  	num=0;while(!(x%pri[i])) num++,x/=pri[i];	  	ll k=(pri[i]-1)*modd;		ans=(ans*((mi(pri[i],num*b+1,k)+k-1)/(pri[i]-1)))%modd;	  }	if(x>1)	{		ll k=(x-1)*modd;		ans=(ans*((mi(x,b+1,k)+k-1)/(x-1)))%modd;	}	printf("%lld/n",ans);	return 0;}