poj1845 数论好题

求a^b的所有因数和。(a,b<=50000000)

分解质因数 a=a1^b1a2^b2...*an^bn

则 因数和为(a1^0+a1^1+...+a1^b1)(a2^0+a2^1+...+a2^b2)...(an^0+an^1+...+an^bn) （乘法原理）

a^b=a1^(b1b)a2^(b2b)...an^(bnb)

因数和为(a1^0+a1^1+...+a1^(b1n))(a2^0+a2^1+...+a2^(b2n))...(an^0+an^1+...+an^(bn*n))

等比数列求和。。a1*(1-q^n)/(1-q)

逆元inv(0)不存在。。坑死。。所以inv(Mo),inv(2*Mo)...都不存在。。

而q-1=kMo时，这一项就相当于b2x+1个1相加。。然后就好办了。。

对逆元的理解还是欠缺的。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#define N 100000
#define Mo 9901
using namespace std;
int a,b,t,cnt;
long long ans=1;
int p[N],prime[N],counter[N];
long long pow(int a,int b,int p){
    long long ret=1,base=a;
    while(b){
        if(b&1) ret=(ret*base)%p;
        base=(base*base)%p;
        b=b>>1;
    }
    return ret;
}
int main(){
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    scanf("%d%d",&a,&b);
    if(a==0) {printf("0\n");return 0;}
    int t=(int)sqrt((double)a);
    fill(p,p+N,1);p[0]=p[1]=0;cnt=0;
    for(int i=2;i<=t;i++)
        if(p[i]) {
            for(int j=i*i;j<=t;j+=i) p[j]=0;
            prime[++cnt]=i;
        }
    int aa=a;
    for(int i=1;i<=cnt;i++)
        while(aa%prime[i]==0) aa/=prime[i],counter[i]++;
    if(aa!=1&&aa!=0) prime[++cnt]=aa,counter[cnt]=1;
    for(int i=1;i<=cnt;i++){
        if((prime[i]-1)%Mo==0) {ans=(ans*(counter[i]*b+1))%Mo;continue;}
        long long tmp=(pow(prime[i],counter[i]*b+1,Mo)+Mo-1)%Mo;
        ans=(ans*tmp)%Mo;
        ans=(ans*pow((prime[i]-1)%Mo,Mo-2,Mo))%Mo;
    }
    printf("%lld\n",ans);
    return 0;
}