poj1845 A^B 的因子和 (逆元)

2017年04月26日 10点热度 0人点赞 0条评论
Sumdiv
Time Limit: 1000MS   Memory Limit: 30000K
Total Submissions: 21310   Accepted: 5360

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

Hint

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). 

逆元知识http://blog.csdn.net/acdreamers/article/details/8220787

//本题的思路非常巧妙
//题目大意是求A^B的所有约数(即因子)之和,并对其取模9901再输出
//此处用的等比数列求和公式和用到逆元的知识:a/b mod c = (a mod (b*c))/ b  
//二分亦可解之 
//int 2147483648~2147483647 大约是2*10^9 
#include
#include
using namespace std;
#define ll long long
const int mod=9901;
ll Mod;
ll A,B;
ll fast_multi(ll x,ll y){
	ll ans=0;
	while(y){
		if(y&1) ans=(ans+x)%Mod;
		y>>=1;
		x=(x+x)%Mod;
	}
	return ans;
}
ll fastpow(ll P,ll n){//快速幂
	ll ans=1;
	while(n){
		if(n&1) ans=fast_multi(ans,P);//两数直接相乘溢出 
		n>>=1;
		P=fast_multi(P,P);//两数直接相乘溢出
	}
	return ans;
}
int main(){
	while(~scanf("%lld%lld",&A,&B)){
		int n;
		int ans=1;
		for(int i=2;i*i<=A;i++){//如果改成i<=A,则i最后是一个很大的素数 
			if(A%i==0){
				n=0;
				while(A%i==0){
					n++;
					A/=i;
				}
				Mod=mod*(i-1);
				ans=(ans*(fastpow(i,B*n+1)-1)/(i-1))%mod;//B*n+1超出了int的范围 
			}
		}
		if(A>1){
			Mod=mod*(A-1);
			ans=(ans*(fastpow(A,B+1)-1)/(A-1))%mod;
		}
		printf("%dn",ans);
	}
	return 0;
}
未经允许不得转载!poj1845 A^B 的因子和 (逆元)

update

纸上得来终觉浅, 绝知此事须躬行。