正文
一看到题目142857，就想到了1/7.然后瞎猜应该和分数有关。
先在十进制下推，
假设我们有个循环数，比如142857.
令(x=0.14285714.... =(q/p) (gcd(p,q)==1))
则
(x=0.142857142857……)
(2x=0.285714285714……)
(3x=0.428571428571……)
(4x=0.571428571428……)
(5x=0.714285714285……)
(6x=0.857142857142……)
(x=0.142857142857……)
(10x=1.428571428571……)
(100x=14.285714285714……)
(1000x=142.857142857142……)
(10000x=1428.571428571428……)
(100000x=14285.714285714285……)
因为x是一个无限纯循环小数，所以(gcd(10,p)=1).
根据循环数的定义，他们的尾数相同。
所以，x是循环数(Longleftrightarrow){(x),(2x),(3x),...,(6x)}的小数部分与{(10^0x),(10^1x),...,(10^5x)}相同.
(Longleftrightarrow){(q/p),(2q/p),(3q/p),...(6q/p)}的小数部分与{(10^0q/p),(10^1q/p),...,(10^5q/p)}相同(均不考虑顺序)
(ecause gcd(p,q)=1)
( herefore)小数部分只由(modspace p)的余数唯一确定。
故上式等价于{(q,2q,3q,...)}与{(10^0q,10^1q,10^2q,...)}在mod p意义下相同。
(ecause gcd(p,q)=1)
必有(aqequiv1(mod space p))
将上式同乘a,得到
{(1,2,3,4,5,6)}与{(10^0,10^1,...,10^5)}在mod p意义下相同。
显然{(1,10,...,10^5)}中有一个数模p余2.事实上它是100
(这里当然可以假设一个数推下去，但是结论是一样的，所以就直接未卜先知了)
且{(10^0,10^1,...,10^5)}与{(10^2,...,10^7)}在mod p意义下相同(循环数的性质)。
所以{(10^0,10^1,...,10^5)}与{(2*10^0,...,2*10^5)}在mod p意义下相同(循环数的性质)。
显然,{(1,2,3,4,5,6)}与{(2,4,6,8,10,12)}在mod p意义下相同。
( herefore) {(1,3,5)}与{(8,10,12)}在mod p意义下相同。
易知(p<8)
另一方面
显然有p>循环节长度。否则x*p将得到一个整数，不会循环下去。
( herefore) (p>6)
( herefore) (p=7)
上述论证在n≠6的时候仍然成立：p=循环节长度+1.
那么就有{(1,2,...,p-1)}和{(10^0,10^1,...,10^{p-2})}在mod p意义下相同
( herefore) 那么就有{(2,...,p-1)}和{(10^1,...,10^{p-2})}在mod p意义下相同
我们发现(10^1,...,10^{p-2})中没有一个模p余1的数
即(1,...,p-2≠phi(p))
所以,p是质数，且10是p的原根
推广到b进制下，当且仅当p是质数且b是p的原根时，有循环数
这个时候我们就要掌握到一个求原根方法
求质数x的原根:
求出(x-1)所有不同的质因子(p_1,p_2...p_m).
对于任何(a(2<=a<=x-1)),判定a是否为x的原根，只需要检验(a^{(x-1)/p_1},a^{(x-1)/p_2},...,a^{(x-1)/p_m})这m个数中，是否存在一个数(mod x)为1，若存在，a不是x的原根，否则就是x的原根。
对于合数，将x-1换成(phi (x))即可
证明：原文
假设存在一个(t<phi(x)=x-1)使得(a^t = 1 (mod space x))
那么由裴蜀定理，一定存在一组k,r使得(kt=(x-1)r+gcd(t,x-1))
而由欧拉定理有，$a^{x-1} = 1 pmod {x} $
于是$1 = a^{kt} = a^{xr-r+gcd(t,x-1)} = a^{gcd(t,x-1)}pmod{x} $
而(t<x-1)故(gcd(t,x-1)<x-1)
又(gcd(t,x-1)|x-1)于是(gcd(t,x-1))必整除((x-1)/p_1,(x-1)/p_2...(x-1)/p_m)其中至少一个，设其一为((x-1)/p_i)
那么(a^{(x-1)/pi} = (a^{gcd(t,x-1)})^s = 1^s = 1 (mod x))
这与假设矛盾
所以只需要将小于x-1的b逐个判断是不是p的原根就行了。
使用快速幂时间复杂度为(Theta(sqrt{q}log{q}))
但实际复杂度远远小于。过了就行
代码
/*
@Date : 2018-08-08 00:45:35
@Author : Adscn
@Link : https://www.luogu.org/blog/LLCSBlog/
*/
#include<bits/stdc++.h>
using namespace std;
#define IL inline
#define RG register
#define gi getint()
#define pi(k) putint(k)
#define gc getchar()
#define File(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
IL int getint()
{
RG int xi=0;
RG char ch=gc;
bool f=0;
while(ch<'0'|ch>'9')ch=='-'?f=1:f,ch=gc;
while(ch>='0'&ch<='9')xi=(xi<<1)+(xi<<3)+ch-48,ch=gc;
return f?-xi:xi;
}
IL void putint(int k)
{
if(k<0)k=-k,putchar('-');
if(k>=10)putint(k/10);
putchar(k%10+'0');
}
IL unsigned int LOG2(unsigned int x)
{
unsigned int ret;
__asm__ __volatile__ ("bsrl %1, %%eax":"=a"(ret):"m"(x));
return ret;
}
long long n,x;
const int MAX=5*1e6+1;
long long mod;
long long ksm(long long a,int b)
{
long long ans=1,tmp=a;
while(b)
{
if(b&1)ans=(ans*tmp)%mod;
tmp=(tmp*tmp)%mod;
b>>=1;
}
return ans;
}
IL bool checkp(long long p)
{
if(p<2)return false;
if(p==2||p==3)return 1;
for(long long i=2;i*i<=p;i++)if(p%i==0)return false;
return true;
}
IL bool check(long long k)
{
if(k%mod==0)return false;
for(long long i=1;i*i<=n;i++)
{
if(n%i==0)
{
if(i<n&&ksm(k,i)==1)return false;
if(i!=1&&ksm(k,n/i)==1)return false;
}
}
return true;
}
int main(void)
{
// File("number");
cin>>n>>x;
// getEuler();
mod=n+1;
if(!checkp(mod))return printf("-1")&0;
for(int i=x-1;i>=2;i--)if(check(i))return printf("%d",i)&0;
printf("-1");
return 0;
}