题目描述

blablabla

样例

blablabla

算法1

O($sqrt(n)$)

时间复杂度分析：200000的固定计算量+sqrt(n)

C++ 代码

#include<bits/stdc++.h>
using namespace std;

#define go(i,a,b) for(int i=a;i<=b;++i)
#define int long long
typedef long long ll;

const int mod[6]={0,2,3,4679,35617,999911659};

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
int n,q,a[5],jc[36005][6];

template<typename T> inline void read(T &x){
    x=0;char f=1,c=getchar();
    while(!isdigit(c)){ if(c=='-') f=-1; c=getchar(); }
    while(isdigit(c)){ x=x*10+c-'0'; c=getchar(); }
    x*=f;
}

int qpow(int x,int p,const int &id){
    int ans=1;
    for(;p;p>>=1){
        if(p&1) ans=ans*x%mod[id];
        x=x*x%mod[id];
    }
    return ans;
}

int C(int n,int m,const int &id){
    if(m>n) return 0;
    return jc[n][id]*qpow(jc[m][id],mod[id]-2,id)%mod[id]*qpow(jc[n-m][id],mod[id]-2,id)%mod[id];
}

int lucas(int n,int m,const int &id){
    if(!m) return 1;
    return lucas(n/mod[id],m/mod[id],id)*C(n%mod[id],m%mod[id],id)%mod[id];
}

void exgcd(int a,int b,int &x,int &y){
    if(!b)x=1,y=0;
    else exgcd(b,a%b,y,x),y-=x*(a/b);
}

signed main(){
    //freopen("input.txt","r",stdin);
    read(n),read(q);
    go(i,1,4)
        jc[0][i]=1;
    go(t,1,4){
        go(i,1,36000){
            jc[i][t]=jc[i-1][t]*i%mod[t];
        }
    }
    if(q==999911659){
        puts("0");
        return 0;
    }
    int x=n;
    go(t,1,4){
        for(int i=1;i*i<=x;++i){
            if(x%i) continue;
            int j=x/i;
            a[t]+=lucas(n,i,t);
            if(j!=i) a[t]+=lucas(n,j,t);
        }
    }   
    int y;
    int ans=0;
    go(i,1,4){
        int M=999911658/mod[i];
        exgcd(M,mod[i],x,y);        
        ans=(ans+(M*x%999911658*a[i]%999911658+999911658)%999911658)%999911658;
    }
    ans=qpow(q,ans,5);
    cout<<ans;
    return 0;
}