yuyc @ 2023-11-10 08:48:04
#include <bits/stdc++.h>
using namespace std;
int b;
const int mod = 9901;
struct node{
int p = 0,c = 0;
node (int _p,int _c) : p(_p),c(_c){};
};
vector<node> v;
int qmi(int a,int n){
int res = 1;
while(n){
if(n & 1) res = res * a % mod;
n >>= 1;
a = a * a % mod;
}
return res;
}
void cal(int a){
for(int i=2;i<=sqrt(a);i++){
if(a % i == 0){
// node n = {a,0};
v.push_back({i,0});
while(a % i == 0){
a /= i;
v.back().c ++;
}
v.back().c *= b;
}
}
if(a > 1){
v.push_back({a,b});
}
}
int sum(int p,int c){
if(!c) return 1;
if(c & 1){
return ((1 + qmi(p,(c + 1) / 2)) % mod) * (sum(p,(c - 1) / 2) % mod);
}else{
return ((1 + qmi(p,(c / 2) + 1)) % mod) * (sum(p,c / 2) % mod) - qmi(p,c + 1);
//return ((1 + qmi(p,c / 2) % mod) * ((sum(p,c / 2 - 1) % mod)) + qmi(p,c));改成这句就对了
}
}
signed main(){
int a,ans = 1;
cin>>a>>b;
if(a == 0){
cout<<0;
return 0;
}
cal(a);
/* for(int i=0;i<v.size();i++){
cout<<v[i].p<<' '<<v[i].c<<endl;
}*/
for(int i=0;i<v.size();i++){
// cout<<v[i].p<<' '<<v[i].c<<endl;
ans *= sum(v[i].p,v[i].c) % mod;
ans %= mod;
}
cout<<ans;
return 0;
}
by yuyc @ 2023-11-10 08:51:54
当p=13,c=190时,sum(p,c)结果为负数
by yukari1735 @ 2023-11-10 09:35:03
@yuyc 取模完的数做减法要加上模数,比如你在 (a-b+p)%p
这样。
by yukari1735 @ 2023-11-10 09:36:48
@yuyc 以及你的代码似乎在哪里会爆 int
,我全改成 long long
再加上前面的那个就通过了。
by yuyc @ 2023-11-10 09:59:45
@yukari1735 学到了,谢谢你