solution
当(K,M)不互质时肯定无解。
然后就考虑(K,M)互质的情况。根据欧拉定理(K^{varphi(M)}equiv 1(mod M)),我们可以得到一个可能的答案(varphi(M)),但是(varphi(M))不一定是一个最小解。
先说结论:满足条件的最小解一定是(varphi(M))的因子。
证明:假设存在一个最小的(x)满足(x<varphi(M)且x mid varphi(M))使得(K^xequiv 1(mod M))。那么我们取一个最大的(k)使得(kx<varphi(M))。联合(K^{kx}equiv 1(mod M))和(K^{varphi(M)}equiv 1(mod M))我们可以得到(K^{varphi(M) - kx}equiv 1(mod M)),又因为(varphi(M)-kx<x),所以(x)不是一个最小解。
所以思路就很简单了,枚举(varphi(M))的因子(x),并且计算(K^x\%M),找到最小的合法解即可。
code
/*
* @Author: wxyww
* @Date: 2020-04-22 21:49:03
* @Last Modified time: 2020-04-22 21:53:29
*/
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
using namespace std;
typedef long long ll;
ll read() {
ll x = 0,f = 1;char c = getchar();
while(c < '0' || c > '9') {
if(c == '-') f = -1; c = getchar();
}
while(c >= '0' && c <= '9') {
x = x * 10 + c - '0'; c = getchar();
}
return x * f;
}
int mod;
int phi(int x) {
ll ret = 1;
for(int i = 2;i * i <= x;++i) {
if(x % i == 0) {
ret *= (i - 1);
x /= i;
}
while(x % i == 0) {
ret *= i;
x /= i;
}
}
if(x != 1) ret *= (x - 1);
return ret;
}
ll qm(ll x,ll y) {
ll ret = 1;
for(;y;y >>= 1,x = x * x % mod)
if(y & 1) ret = ret * x % mod;
return ret;
}
int gcd(int x,int y) {
return !y ? x : gcd(y,x % y);
}
int main() {
mod = read();int K = read();
int p = phi(mod);
if(gcd(mod,K) != 1) {
puts("Let's go Blue Jays!");
return 0;
}
int ans = p;
for(int i = 1;i * i <= p;++i) {
if(p % i == 0) {
if(qm(K,i) == 1) ans = min(ans,i);
if(i * i != p)
if(qm(K,p / i) == 1) ans = min(ans,p / i);
}
}
cout<<ans;
return 0;
}