C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 484K, 提交时间: 2018-07-28 10:38:46

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set>
#include<ctime>
using namespace std;
typedef long long ll;
bool check(int n)
{
	for(int i=2;i*i<=n;i++)
		if(n%i==0)return 0;
	return 1;
}
int Pow(int a,int b,int c)
{
	int ans=1;
	while(b)
	{
		if(b&1)ans=(ll)ans*a%c;
		a=(ll)a*a%c;
		b>>=1;
	}
	return ans;
}
int n,x;
vector<int>v;
void deal(int n)
{
	v.clear();
	for(int i=2;i*i<=n;i++)
		if(n%i==0)
		{
			v.push_back(i);
			while(n%i==0)n/=i;
		}
	if(n>1)v.push_back(n);
}
bool Solve(int x)
{
	for(int i=0;i<v.size();i++)
		if(Pow(x,n/v[i],n+1)==1)return 0;
	return 1;
}
int main()
{
	scanf("%d%d",&n,&x);
	if(x==2||!check(n+1))printf("-1\n");
	else
	{
		deal(n);
		int ans=-1;
		for(int i=x-1;i>=2;i--)
			if(Solve(i))
			{
				ans=i;
				break;
			}
		printf("%d\n",ans);
	}
}

C++(clang++11) 解法, 执行用时: 2ms, 内存消耗: 388K, 提交时间: 2021-05-08 14:54:37

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
bool isprime(int n)
{
    for(int i=2;i*i<=n;i++)
        if(n%i==0)return false;
    return true;
}
ll qpow(ll a,ll n,ll mod)
{
    ll ans=1;
    for(;n;n>>=1,a=a*a%mod)
        if(n&1) ans=ans*a%mod;
    return ans;
}
bool isroot(int x,int p)
{
    for(int i=2;i*i<=p-1;i++)
        if((p-1)%i==0)
        if(qpow(x,i,p)==1||qpow(x,(p-1)/i,p)==1)
        return false;
    return true;
}
int main()
{
    int n,x;
    cin>>n>>x;
    if(isprime(n+1))
	{
        for(int i=x-1;i>=2;i--)
            if(isroot(i,n+1))
			{
                printf("%d\n",i);
                return 0;
            }
    }
    printf("-1\n");
    return 0;
}