Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## 没有用逆元，根据卷积的性质进行二分，快速写0S

Posted by tinyme at 2018-09-30 14:49:33 on Problem 1845
```#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int mod=9901;
const int N=7100;
#define ll long long
int prime[N+1];
void get_prime(){
for(int i=2;i<=N;i++){
if(!prime[i])prime[++prime[0]]=i;
for(int j=1;j<=prime[0]&&i*prime[j]<=N;j++){
prime[i*prime[j]]=1;
if(i%prime[j]==0)break;
}
}
}
int factor[100][2],fatCnt;
void get_factor(ll x){
memset(factor,0,sizeof factor),fatCnt=0;
for(int i=1;i<=prime[0];i++){
if(x%prime[i]==0){
factor[fatCnt][0]=prime[i];
while(x%prime[i]==0)x/=prime[i],factor[fatCnt][1]++;
fatCnt++;
}
}
if(x!=1)factor[fatCnt][0]=x,factor[fatCnt++][1]=1;
}
ll Pow(ll a,ll b){
ll ans=1;
while(b){
if(b&1)ans=ans*a%mod;
a=a*a%mod;
b>>=1;
}
return ans;
}
ll sum(ll p,ll n){
if(p==0)return 0;
if(n==0)return 1;
if(n&1) return ((1+Pow(p,n/2+1))%mod*sum(p,n/2)%mod)%mod;
else return ((1+Pow(p,n/2+1))%mod*sum(p,n/2-1)+Pow(p,n/2)%mod)%mod;
}
ll slove(ll A,ll B){
get_factor(A);
ll ans=1;
for(int i=0;i<fatCnt;i++){
ans*=sum(factor[i][0],B*factor[i][1])%mod;
ans%=mod;
}
return ans;
}
int main(){
get_prime();
ll A,B;
while(cin>>A>>B) cout<<slove(A,B)<<endl;
}
```

Followed by: