88pts求助

majingxuan123 @ 2024-07-06 20:10:23

#include<iostream>
using namespace std;
int a,b;
int p[20],c[20],m;
void divide(int x){
    for(int i=2;i<=x/i;i++){
        if(x%i==0){
            p[++m]=i;
            while(x%i==0)x/=i,c[m]++;
        }
    }
    if(x>1)p[++m]=x,c[m]=1;
}
int mod=9901;
int power(int a,long long b){
    int ans=1;
    while(b){
        if(b&1)ans=(long long)ans*a%mod;
        a=(long long)a*a%mod;
        b>>=1;
    }
    return ans;
}
int main(){
    cin>>a>>b;
    if(a==0){
        cout<<0;
        return 0;
    }
    divide(a);
    int ans=1;
    for(int i=1;i<=m;i++){
        if(!(p[i]-1)%mod){
            ans=((long long)b*c[i]+1)%mod*ans%mod;
        }   
        else{
            int x=power(p[i],(long long)b*c[i]+1);
            x=(x-1+mod)%mod;
            int y=power(p[i]-1,mod-2);
            ans=(long long)ans*x%mod*y%mod;
        }
    }
    cout<<ans;
    return 0;
}

by JHR100330 @ 2024-07-18 19:06:58

@majingxuan123

#include<iostream>
using namespace std;
int a,b;
int p[20],c[20],m;
void divide(int x){
    for(int i=2;i<=x/i;i++){
        if(x%i==0){
            p[++m]=i;
            while(x%i==0)x/=i,c[m]++;
        }
    }
    if(x>1)p[++m]=x,c[m]=1;
}
int mod=9901;
int power(int a,long long b){
    int ans=1;
    while(b){
        if(b&1)ans=(long long)ans*a%mod;
        a=(long long)a*a%mod;
        b>>=1;
    }
    return ans;
}
int main(){
    cin>>a>>b;
    if(a==0){
        cout<<0;
        return 0;
    }
    divide(a);
    int ans=1;
    for(int i=1;i<=m;i++){
        if(!((p[i]-1)%mod)){ //只修改一下这里即可，优先级问题
            ans=((long long)b*c[i]+1)%mod*ans%mod;
        }   
        else{
            int x=power(p[i],(long long)b*c[i]+1);
            x=(x-1+mod)%mod;
            int y=power(p[i]-1,mod-2);
            ans=(long long)ans*x%mod*y%mod;
        }
    }
    cout<<ans;
    return 0;
}

! 的优先级在 % 之前，会优先计算 !，故而导致错误，加一个括号改变一下优先级即可，也可写成if((p[i]-1)%mod==0){

给个关注谢谢

by majingxuan123 @ 2024-07-19 07:52:55

感谢大佬

orz

已关