poj1845sumdiv

题意

求$A^B$的所有约束之和mod9901.

思路

A可以写成

$p_1^c1*p_2^c2*……*p_n^cn$

然后

$A^B可以写成p_1^c1^B*p_2^c2*B*……*p_n^cn*^B$ $然后A^B的约数可以写成$ $(1+p_1+p_1^2+……+p_1^c1^B)*(1+p_2+p_2^2+……+p_2^c2*B)*…… *(1+p_n+p_n^2+……+p_n^cn*^B)$

而等比数列的公式可以写成

$(p_1^b*^c_1+1)/(p_1+1)$ $(p_1-1)不是9901的倍数时可以用逆元求出但当(p_1-1)是9901的倍数时，无法求逆元$ $这时p_1模除9901时余1这时带入(1+p_i+p_i^2+……+p_i^ci*B)得到B*c_1+1$

这样问题就得以解决。

代码

#include<iostream>
using namespace std;
const int mod=9901;
int a,b;
int p[20],c[20];
int m=0;
void divide(int x){
    for(int i=2;i*i<=x;i++){
        if(x%i==0){
            p[++m]=i;
            c[m]=0;
            while(x%i==0) x/=i,c[m]++;
        }
    }
    if(x>1) p[++m]=x,c[m]=1;
}
long long ksm(long long a,long long b) {
	int c = 1;
	while(b){
		if(b&1) c=c*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return c;
}
int main(){
    cin>>a>>b;
    long long ans=1;
    divide(a);
    for(int i=1;i<=m;i++){
        if((p[i]-1)%mod==0){
            ans=(b*c[i]+1)%mod*ans%mod;
        }
        else{
            long long x=(ksm(p[i],b*c[i]+1)-1+mod)%mod;
            x*=ksm(p[i]-1,mod-2)%mod;
            ans=ans*x%mod;
        }
    }
    cout<<ans<<endl;
}