题解 P4861 【按钮】
顾z
2018-11-05 09:50:49
这题太水了吧 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);
}
```