记录编号	158302	评测结果	AAAAAAAAAA
题目名称	[CF 303D]循环数	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2015-04-14 14:34:20	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
LL quickpow(LL a,LL n,LL m){
	LL ans=1;
	while(n){
		if(n&1) ans=(ans*a)%m;
		a=(a*a)%m;
		n>>=1;
	}
	return ans;
}
bool is_prime(LL p){
	if(p<2) return false;
	for(LL i=2;i*i<=p;i++){
		if(i<p&&p%i==0) return false;
	}
	return true;
}
bool is_root(LL a,LL p){//a是否为p的原根
	if(a%p==0) return false;
	for(LL i=1;i*i<=p-1;i++){
		if((p-1)%i==0){
			if(i<p-1&&quickpow(a,i,p)==1) return false;
			if((p-1)/i<p-1&&quickpow(a,(p-1)/i,p)==1) return false;
		}
	}
	return true;
}
int main(){
	freopen("rotatablenumber.in","r",stdin);
	freopen("rotatablenumber.out","w",stdout);
	LL N,X;
	cin>>N>>X;
	if(!is_prime(N+1)) cout<<-1<<endl;
	else{
		for(LL b=X-1;b>1;b--){
			if(is_root(b,N+1)){
				cout<<b<<endl;
				return 0;
			}
		}
		cout<<-1<<endl;
	}
	return 0;
}