四、阅读程序3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

#include<iostream>
#define mod 9901
using namespace std;
int a,b,sa,cal[10010][2],cnt=0,ans=1;
int f(int ml,int nl){
    int s=1;
    while(nl>0){
        if(nl&1){
            s=s*ml%mod;  
        }
    ml=ml*ml%mod;
    nl=nl>>1;
    }
return s%mod;
}
int s(int x,int y){
    int res=0;
    y=y*b;
    if(x%mod==1){
        res=(y+1)%mod;
    }
    else{       
        res=(f(x%mod,y+1)-1)%mod * f((x-1)%mod,mod-2)%mod;
    }
return res%mod;
}
int main(){
    cin>>a>>b;
    if(a==0){
       cout<<0<<endl;
       return 0;
    }   
   for(int i=2;i*i<=a;i++){
      if(a%i==0){
          cnt++;
          cal[cnt][0]=i;
          cal[cnt][1]=1;
          a=a/i;
          while(a%i==0){
              cal[cnt][1]++;
              a=a/i;
          }
        }
    }
    
    if(a!=1){
       cnt++;
       cal[cnt][0]=a;
       cal[cnt][1]=1;
    }
    
                                                                                                                                                                 
    for(int i=1;i<=cnt;i++){
        ans=ans*s(cal[i][0],cal[i][1])%mod;
    }
    
    cout << (ans%mod+mod)%mod;
return 0;
}