AT_arc172_e题解

· · 题解

从打表到打表的好题。

1 题意

给定一个数 x，满足 1\le x<10^9 且 x 既不是 2 的倍数也不是 5 的倍数（即 \gcd(x,10)=1），求最小的 n 满足 n^n\equiv x\pmod{10^9}，若无解输出 -1。

多次（最多 10^4 次）询问。

2 思路

省流：对于每个 1\le y<5\times10^6 且 \gcd(y,10)=1，预处理出满足 i^i\equiv y\pmod{5\times10^6} 的最小的 i（一定存在且只存在一个 1\le i<5\times10^6 的解）。询问 x 时，对于 y=x\bmod(5\times10^6)，\Theta(1) 得到对应的 i，它就是 n\bmod(5\times10^6) 的值，然后简单枚举 n 判断即可。

首先想到预处理出每个 x 的答案，对于每次询问 \Theta(1) 回答。

显然我们无法估计 n 的上限，时间复杂度不可接受。

显然，当 n 是 2 的倍数时，n^n\bmod{10^9} 也是 2 的倍数，这与 x 的限制矛盾，这意味着 n 不可能是 2 的倍数，同理也不可能是 5 的倍数。

考虑到 x 既不是 2 的倍数也不是 5 的倍数，我们只需要对 4\times10^8 个 x 预处理答案即可。

开始新一轮打表，暂时只考虑 n<10^9 的情况（一共 4\times10^8 个）所产生的所有 n^n\bmod10^9，惊讶地发现产生了刚好 4\times10^8 个本质不同的结果，这意味着，n 和 x 形成了一个双射，也就是说不可能无解且 n 有了一个清晰的限制（10^9）。

显然预处理出这 4\times10^8 种可能同样是无法接受的。

根据欧拉函数相关性质，当 \gcd(a,m)=1 时，a^{\varphi(m)}\equiv1\pmod m。事实上，在本题 m=10^9 的情况下，上式可写为 a^{5\times10^6}\equiv1\pmod m，即使 5\times10^6 远小于 \varphi(10^9)。

回到这题，显然：

n^{n\bmod(5\times10^6)}\equiv n^n\pmod{10^9}

因为 5\times10^6 是 10^9 的因数，所以：

n^{n\bmod(5\times10^6)}\equiv n^n\pmod{5\times10^6} [n\bmod(5\times10^6)]^{n\bmod(5\times10^6)}\equiv n^n\pmod{5\times10^6}

同时：

[n\bmod(5\times10^6)]^{n\bmod(5\times10^6)}\equiv n^n\equiv x\bmod(5\times10^6)\pmod{5\times10^6}

而预处理满足要求的 n\bmod(5\times10^6) 的时间复杂度是可以接受的，那么 \Theta(1) 得出 n\bmod(5\times10^6) 后，枚举 n 即可得出答案，显然最多枚举 200 个。

3 代码与记录

#include<bits/stdc++.h>
using namespace std;
#define mod 1000000000ll
#define eu 5000000ll
long long a[eu+2];
int q;
long long ans=0;
long long qp(long long a,long long b,long long p=mod){
    long long res=1;
    while(b){
        if(b&1)res=res*a%p;
        a=a*a%p; b>>=1;
    }
    return res;
}
int main(){
    #ifndef ONLINE_JUDGE
    freopen("e_1.in","r",stdin);
    freopen("e_1.out","w",stdout);
    #endif
    memset(a,0,sizeof(a));
    for(int i=1;i<=eu;++i){
        if(i%2==0||i%5==0)continue;
        long long w=qp(i,i,eu);
        if(!a[w])a[w]=i;
    }
    scanf("%d",&q);
    for(int ca=1;ca<=q;++ca){
        long long x,y;
        scanf("%lld",&x); y=x%eu;
        ans=a[y];
//      printf("x=%lld y=%lld\n",x,y);
        for(;;ans+=eu){
            if(qp(ans,ans)==x){printf("%lld\n",ans); break;}
        }
    }
    return 0;
}

提交记录

By dengziyue