CF303D 题解

· · 题解

分析证明

首先我们先设这个整数是 \overline{a_1a_2a_3...a_n} ，那么我们不妨设一个有理数 \frac{q}{p}=\overline{0.a_1a_2a_3...a_na_1a_2a_3...a_na_1a_2a_3...a_n...} ，其中 \operatorname{gcd}(p,q)=1

我们设 \operatorname{float}(x) 表示 x 的小数部分。

根据循环数的定义，有

\{\operatorname{float}(\frac{q}{p}),\operatorname{float}(\frac{2q}{p}),...,\operatorname{float}(\frac{nq}{p})\} =\{\operatorname{float}(\frac{q}{p}),\operatorname{float}(\frac{bq}{p}),...,\operatorname{float}(\frac{b^{n-2}q}{p})\}

显然 \operatorname{float}(\frac{a}{p})=\operatorname{float}(\frac{b}{p}) 等价于 \frac{a}{p}-\frac{b}{p} \in Z 等价于 a \equiv b\mod p

又因为 \operatorname{gcd}(p,q)=1，所以 \{1,2,...,n\} =\{1,b,...,b^{n-2}\} 。

易得 p \gt n。

因此 \exists i,b^i=2。

容易发现的是，实际上 \forall i,\{1,2,...,n\} =\{b^i,b^{i+1},...,b^{i+n-2}\}。

根据以上两行我们得到 \exists i,\{1,2,...,n\}=\{b^i,b^{i+1},...,b^{i+n-2}\}=\{2,2b,...,2b^{n-2}\}=\{2,4,...,2n\}。

接着我们分类讨论

首先,n=2m+1 时，去掉相同项之后可得 \{1,3,...,n\}=\{2m+2,2m+4,...,2n\}

于是就有了 0\lt n+1\mod p\le n ,那么显然 p\lt n+1 ，和之前矛盾，舍去。

再看 n=2m 时，同理可得 \{1,3,...,n-1\}=\{2m+2,2m+4,...,4m\}

于是就有了 0\lt n+2\mod p\le n-1 ,那么显然 p\lt n+2

于是 p=n+1 。

而此时显然有 \{b^1,b^2,...,b^{p-1}\}=\{1,2,...,p-1\}，因此 b 是 p 的原根。

又， \{b^1,b^2,...,b^{p-1}\}=\{1,2,...,p-1\} ，因此p是质数。

故我们需要求出的就是 x 内最大的原根。若 p 不是质数就直接输出 -1。

从 x 开始倒着枚举并且一个个判断过去，不难证明当 p 有原根的时候最多枚举 p 次。

代码

#include<bits/stdc++.h>
using namespace std;
int prime[6000003],vis[6000003];
int cnt=0;
void find(int n)
{
    prime[1]=0;
    for (int i=2;i<=n;++i)
    {
        if (!vis[i]) prime[++cnt]=i; 
        for (int j=1;j<=cnt && i*prime[j]<=n;++j)
        {
            vis[i*prime[j]]=1;
            if (i%prime[j]==0) break;
        }
    }
    return; 
}
int n,x,p,a[6000003],tot=0;
void get(int x){
    for(int i=1;i<=cnt;i++) if(!(x%prime[i])) a[++tot]=prime[i];
}
long long qpow(long long a, long long n, long long m)
{
    long long ans = 1;
    while(n){
    if(n&1){ans=(ans * a) % m;}
    a=(a*a)%m;
    n>>=1;
    }
    return ans;
}
bool check(long long x){
    for(int i=1;i<=tot;i++) {
    if(qpow(x,(p-1)/a[i],p)==1) 
    return 0;   
    }
    return 1;
} 
int main(){
    int n,x;
    cin>>n>>x; 
    p=n+1;
    if((qpow(2,p-1,p)!=1 || qpow(3,p-1,p)!=1 || qpow(5,p-1,p)!=1) && p!=2 && p!=3 && p!=5){
    printf("-1");
    return 0;
    }
    find(p);
    get(p-1);
    for(int i=x-1;i>1;i--)
    if(check(i)){
    printf("%d",i);
    return 0;
    }       
    printf("%d",-1);
}