题解 P4861 【按钮】

顾z

2018-11-05 09:50:49

Solution

这题太水了吧 emmm(竟然是个紫题??) ~~之前同桌出过这题,所以就切了[@王小呆](https://www.cnblogs.com/wangxiaodai/)~~ 很容易发现,我们需要求解的是这个东西$K^x \equiv 1(mod\ m)$ 突然想到一个定理.--->**欧拉定理**:$a^{\phi(p)} \equiv 1 (mod\ p) $ 这个定理有解的情况是$gcd(a,p)=1$ 因此判断无解就是$gcd(a,p)!=1$了. ~~但是这题没有设置判断无解的分数,差评。(别问我怎么知道的。qwq~~ 然后我们求解$\phi(p)$即可。 $$\phi(x)=x \times \prod_{i=1}^{r} (1-\frac{1}{p_i})$$ 其中$p_i$为质数 但这**不一定是最小整数解,怎么办?** 枚举$\phi(p)$的因子就好了啊. 这个具体证明挺简单的,如果大家不会我再填坑好了。 所以就不打算证明。 我们$O(\sqrt n)$的求出$\phi(n)$再$O(\sqrt{\phi(n)})$的枚举其因子就好了。 $O(\sqrt n)$求$\phi(n)$就不多说了,相信大家都会。~~其实是我懒~ 如果不会的话,可以去[@王小呆](https://www.cnblogs.com/wangxiaodai/)里面找一找,应该会有。 还有,吐槽一下数据很水。 取模写成对$\phi(n)$取模,竟然有$90pts$。 ``代码`` ```c++ #include<cstdio> #include<algorithm> #include<iostream> #define int long long #define R register using namespace std; inline void in(R int &x) { int f=1;x=0;char s=getchar(); while(!isdigit(s)){if(s=='-')f=-1;s=getchar();} while(isdigit(s)){x=x*10+s-'0';s=getchar();} x*=f; } int n,m,ans=2147483647666LL; int gcd(R int x,R int y){return y==0 ? x:gcd(y,x%y);} inline int phi(R int x) { R int res=x; for(R int i=2;i*i<=x;i++) { if(x%i==0) { res=res/i*(i-1); while(x%i==0)x/=i; } } if(x>1) res=res/x*(x-1); return res; } inline int ksm(R int x,R int y) { R int res=1; for(;y;y>>=1,x=x*x%n) if(y&1)res=res*x%n; return res; } signed main() { in(n),in(m); if(gcd(n,m)!=1) { puts("Let's go Blue Jays!"); return 0; } R int tmp=phi(n); for(R int i=1;i*i<=tmp;i++) { if(tmp%i!=0)continue; if(ksm(m,i)%n==1) { ans=i; break; } if(ksm(m,tmp/i)%n==1)ans=min(ans,tmp/i); } printf("%lld",ans); } ```