自动搬运

查看原文

来自洛谷，原作者为

	da32s1da **

搬运于2025-08-24 22:04:40，当前版本为作者最后更新于2018-10-29 06:58:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先我们看出题目要求$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);//输出答案
    }
}