题解 P4861 【按钮】

· · 题解

首先我们看出题目要求K^x\equiv1 \mod{M}的最小正整数x。

于是我们可以打个扩展BSGS

但我们发现开始是1，结束是1。就想到用幂的循环节来做。

即k^{\phi(M)}\!\!\mod M =1。

输出\phi(M)，试了几组，发现不对

可以发现答案都是\phi(M)的约数，于是我们记录下其约数后，对于每一个约数，我们试着除掉它之后可不可行，若可行则除掉，否则保留。

另外无解情况：若\gcd(K,M)\ !=1，则无解。

因为k^{x}\!\!\mod M一定是\gcd(K,M)的倍数。

#include<cstdio>
#include<algorithm>
using namespace std;
int tim[1000],tot,pri[1000];
int n,m,res=1,p,mm;
int get_phi(int r){    
    int ans=r;
    if(r&1^1)ans>>=1;
    while(r&1^1)r>>=1;
    for(int i=3;i*i<=r;i+=2)  
    if(r%i==0){    
        ans-=ans/i;    
        while(r%i==0)r/=i;
    }   
    if(r>1)ans-=ans/r;    
    return ans;    
}
int ksm(int u,int v,int a){
    int res=1;
    for(;v;v>>=1,u=1ll*u*u%a)
    if(v&1)res=1ll*res*u%a;
    return res;
}
int gcd(int u,int v){return v?gcd(v,u%v):u;}
int main(){
    scanf("%d%d",&n,&m);
    if(gcd(n,m)!=1)puts("Let's go Blue Jays!");//无解
    else{
        p=get_phi(n);//得到phi
        mm=p;
        for(int i=2;(i*i)<=mm;i++){
            if(mm%i)continue;
            pri[++tot]=i;
            while(mm%i==0){
                mm/=i;
                tim[tot]++;
            }
        }
        if(mm!=1){
            pri[++tot]=mm;
            tim[tot]=1;
        }
        //pri[]是因子，tim[]是每个因子出现次数
        int ss=1,qq=p;
        while(ss<=tot){//枚举每个因子
            for(int i=1;i<=tim[ss];i++){//枚举出现次数
                if(ksm(m,qq/pri[ss],n)==1)qq/=pri[ss];
                else break;
                //若除掉该因子可行，则除掉，否则保留
            }
            ss++;
        }
        printf("%d\n",qq);//输出答案
    }
}