「Luogu P4861」按钮 解题报告

题面

输入 $M,K \in [2,2\times 10^9]$，求最小的 $x$，满足：$K^x\equiv 1\pmod {M}$

解题思路

欧拉定理

分析

当 $M,K$ 不互质时，必定无解

当 $M,K$ 互质时，显然 $x=\phi(M)$ 为一解，而最小的 $x$ 应是 $\phi(M)$ 的约数，证明如下：

假设 $x_0 \nmid\ \phi(m)$ 且 $x_0$ 是 $K^x\equiv 1 \pmod M$ 的最小整数解，那么 $x_1=\phi(M)\mod x_0$ 必也是一个解且小于 $x_0$ 与假设不符，因此，最小的解必为 $\phi(M)$ 的约数

枚举 $\phi(M)$ 的约数，再用快速幂判断即可在 $O(\sqrt m\log m)$ 的复杂度内跑过此题

Warning

求 $\phi(M)$ 的时候并不用筛素数，直接 $\sqrt m$ 求即可，(就是因为这个我才得了 $10pts$

Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rll rgt LL
#define inf 0x7f7f7f7f
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
int k,p,t,ans,phi;LL c;
inline int Pow(rint b) {
    rll res=1,a=k;
    for(;b;b>>=1,a=a*a%p)
        if(b&1) res=res*a%p;
    return res;
}
int main()
{
    rint i;
    phi=c=p=read(),k=read();
    for(i=2;(LL)i*i<=c;i++)//直接求phi，因为合数肯定是没有贡献的，
        if(c%i==0) {//并不影响结果
            phi-=phi/i;
            while(c%i==0) c/=i;
        }
    if(c>1) phi-=phi/c;
    if(__gcd(k,p)!=1) printf("Let's go Blue Jays!");
    else {
        ans=phi;
        for(i=2;(LL)i*i<=phi;i++)//枚举
            if(phi%i==0) {
                if(Pow(i)==1) {ans=i;break;}
                if(Pow(phi/i)==1) cmin(ans,phi/i);
            }
        printf("%d",ans);
    }
    return 0;
}