POJ1845 Sumdiv "简单"的逆元 BPM136

我从未想过会WA的这么惨= =

首先显然用分配律可以化为很多等比数列的和的乘积

然后欧拉定理求个逆元

然后....WA了= =

突然发现很多地方乘起来会爆int，赶快换了LL

然后......WA了= =

看了下discuss发现可能没有逆元，在(A-1)%MOD==0时，这时候可以用变换模值：(A/B)%mod=(A%(mod*B))/B%mod

然后……WA了= =

在我怀疑人生的时候发现KSM会爆LL

这细节……

社会社会

 1 /* ***********************************************
 2 Author        :BPM136
 3 Created Time  :2018/7/14 20:23:34
 4 File Name     :1845.cpp
 5 ************************************************ */
 6 
 7 #include<iostream>
 8 #include<cstdio>
 9 #include<algorithm>
10 #include<cstdlib>
11 #include<cmath>
12 #include<cstring>
13 #include<vector>
14 using namespace std;
15 
16 typedef long long LL;
17 
18 const int N = 5e7 + 5;
19 const int M = 5000000;
20 const int MOD = 9901;
21 
22 LL A,B;
23 
24 LL mul(LL a,LL b,LL p) {
25     LL ret=0;
26     for(; b; b>>=1) {
27         if(b&1) ret=(ret+a)%p;
28         a=a*2%p;
29     }
30     return ret;
31 }
32 
33 LL KSM(LL a,LL k,LL mod) {
34     LL ret=1;
35     while(k) {
36         if(k&1) ret=mul(ret,a,mod);
37         a=mul(a,a,mod);
38         k>>=1;
39     }
40     return ret;
41 }
42 
43 LL pri_calc() {
44     LL ret=1;
45     for(int i=2;i*i<=A;i++) {
46         if(A%i) continue;
47         int num=0;
48         while(A%i==0) {
49             A/=i;
50             num++;
51         }
52         if((i-1)%MOD==0) (ret*=KSM(i,B*num+1,MOD*(i-1))/(i-1))%=MOD;
53         else (ret*=( KSM(i,B*num+1,MOD) - 1) * KSM(i-1,MOD-2,MOD) % MOD)%=MOD;
54     }
55     if(A>1) {
56         if((A-1)%MOD==0) (ret*=KSM(A,B+1,MOD*(A-1))/(A-1))%=MOD;
57         else (ret*=(KSM(A,B+1,MOD) - 1) * KSM(A-1,MOD-2,MOD) % MOD)%=MOD;
58     }
59     return (ret%MOD+MOD)%MOD;
60 }
61 
62 int main() {
63     while(cin>>A>>B) {
64 
65         if(A<=1 || B==0) {
66             cout<<1<<endl;
67             continue;
68         }
69         /*
70            LL tmp=1;
71         LL anss=0;
72         for(int i=1;i<=B;i++) tmp=tmp*A;
73         for(int i=1;i<=tmp;i++) if(tmp%i==0) anss+=i;
74         cerr<<anss%MOD<<endl;
75         */
76 
77         LL ans=pri_calc();
78         cout<<ans<<endl;
79     }
80     return 0;
81 }

View Code