本文共 2016 字，大约阅读时间需要 6 分钟。

Description

Input

Output

Sample Input

2 3

Sample Output

15

Hint

题意：求a^b的所有因子之和

解题思路：如果a是素数，我们可以知道a^b的所有因子是1，a，a^2，a^3，...，a^b，

则a^b的所有因子之和为1+a+a^2+a^3+a^4+...+a^b；

如果a不是素数，那么我们可以将a转换为由多个素数组成的合数即a=(p[0]^n[0])*(p[1]^n[1])*(p[2]^n[2])*...*(p[k]^n[k])，（p[0],p[1],p[2],...,p[n]都是素数），

那么a^b转换为p[0]^(n[0]*b) * p[1]^(n[1]*b) * p[2]^(n[2]*b) * ... * p[n]^(n[n]*b)，

则所有因子之和为[(1+p[0]+p[0]^2+...+p[0]^(n[0]*b) )*(1+p[1]+p[1]^2+...+p[1]^(n[1]*b) )*...*(1+p[n]+p[n]^2+...+p[n]^(n[n]*b) )

参考代码：

#include 
   
    #include 
    
     #include 
     
      typedef long long ll;using namespace std;#define m 9901ll mod_pow(ll a,ll b){	//快速幂	ll ans=1;	while (b>0){		if (b&1)			ans=ans*a%m;		a=a*a%m;		b>>=1;	}	return ans;} ll sum(ll p,ll n)  //递归二分求 (1 + p + p^2 + p^3 +...+ p^n)%mod  {                          //奇数二分式 (1 + p + p^2 +...+ p^(n/2)) * (1 + p^(n/2+1))      if(n==0)               //偶数二分式 (1 + p + p^2 +...+ p^(n/2-1)) * (1+p^(n/2+1)) + p^(n/2)          return 1;      if(n%2)  //n为奇数,          return (sum(p,n/2)*(1+mod_pow(p,n/2+1)))%m;      else     //n为偶数          return (sum(p,n/2-1)*(1+mod_pow(p,n/2+1))+mod_pow(p,n/2))%m;  } /* ll sum(ll a,ll b){	//求 1+a^1+a^2+...+a^b的值	ll ans=mod_pow(a,b+1);	return (ans-1)/(a-1);}*/int main(){	int a,b;	int p[10000],n[10000];		while (cin>>a>>b){		int k=0;		memset(n,0,sizeof(n));		for (int i=2;i<=a;i++){	//将a转换为(p[0]^n[0])*(p[1]^n[1])*(p[2]^n[2])*...*(p[k]^n[k])			if (a%i==0){				p[k]=i;				while (a%i==0){					n[k]++;					a/=i;				}				k++;			}		}		ll ans=1;		for (int i=0;i
     
    
   

转载地址：http://dfbqb.baihongyu.com/