题目描述

blablabla

样例

blablabla

算法1

(暴力枚举) $O(n^2)$

直接上模板暴力求逆元就解了
不过大佬的算法似乎快了很多

时间复杂度分析：blablabla

C++ 代码

#include <stdio.h>
#include <iostream>

using namespace std;
typedef long long ll;
const int mod=9901;
const int maxn=5e5+7;
bool prime[maxn];
int p[maxn];
int tp[maxn],tk[maxn];

int quickpow(int a,int b){
    int res=1;
    while(b){
        if(b&1)res=(ll)res*a%mod;
        a=(ll)a*a%mod;
        b>>=1;
    }
    return res;
}

int inv(int a){
    return quickpow(a,mod-2);
}

int getsum(int p,int k){
    return (quickpow(p,k+1)-1)*1ll*inv(p-1)%mod;
}

void getprime(){
    int cnt=0;
    for(int i=2;i<maxn;i++){
        if(!prime[i]){
            p[cnt++]=i;
            for(int j=i<<1;j<maxn;j+=i){
                prime[j]=1;
            }
        }
    }
    return;
}

int main()
{
    getprime();
    int a,b,cnt=0;
    scanf("%d%d",&a,&b);
    if(!a)printf("0\n");
    else{
    for(int i=0;i<maxn;i++){
        if(a==1)break;
        if(!(a%p[i])){
            tp[cnt]=p[i];
            tk[cnt]++;
            a/=p[i];
            while(!(a%p[i])){
                a/=p[i];
                tk[cnt]++;
            }
            cnt++;
        }
    }
    int sum=1;
    for(int i=0;i<cnt;i++){
        sum=(ll)sum*getsum(tp[i],tk[i]*b*1ll)%mod;
    }
    printf("%d\n",(sum+mod)%mod);
    }
    return 0;
}

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度分析：blablabla

C++ 代码

blablabla