AT_arc172_e

· · 题解

题目大意：

给你一个 x，请求出 n，满足 n^n \equiv x \pmod {10^9}，保证 x 与 10^9 互质。

解题思路：

这个 n 肯定也和 10^9 互质，所以合法的 x 的个数和合法的 n 的个数是相同的。
我们举几个例子，会发现所有例子的 x^x 模 10^9 都是不同的。那么猜测对于所有的 1\le a \le 10^9 且 x 与 10^9 互质，x^x 是互不相同的，下面会给出比较粗略的证明。

反证：假设存在两个数 a, b 使得 a < b 且 a^a \equiv b^b \pmod {10^9}。
那么我们把他们分解质因数，a = x_{1}^{y_{1}} \times x_{2}^{y_{2}} \dots b = X_{1}^{Y_{1}} \times X_{2}^{Y_{2}} \dots
然后 a^a = x_{1}^{y_{1} \times a} \times x_{2}^{y_{2} \times a} \dots b^b = X_{1}^{Y_{1} \times b} \times X_{2}^{Y_{2} \times b} \dots
那么他们的每一项都不是 2 或 5，所以他们两个模 10^9 就不同。
感性理解一下吧QWQ。

有了上面的结论，就可以发现，-1 永远不会出现，也就是每个 x 有一个自己的 n。
有了这个条件后，我们可以将问题弱化一下，再去一步一步解决。
我们可以先找到一个 n 使得 n^n \equiv x \pmod {100}，那么预处理就行，那么我们就可以用类似归纳法，从 10^2 推向 10^3，那么只需要枚举一下答案的百位就行了，因为他加一个十位或个位的话就会让他的答案不对，因为对于模每个 10^k 都有唯一的答案。
所以流程就是确定了 100 的答案之后，确定 1000 的答案，一直到 10^9。

CODE：

#include <bits/stdc++.h>
using namespace std;
#define int long long
int qp(int a, int b, int mod){
    int ans = 1;
    while(b){
        if(b % 2) ans = ans * a % mod;
        a = a * a % mod;
        b /= 2;
    }
    return ans;
}

int t, n, f[105], a[10];

void solve(){
    cin >> n;
    a[2] = f[n % 100];
    int pw = 100;
    for(int i = 3; i <= 9; i++){
        for(int j = 0; j <= 9; j++){
            a[i] = a[i - 1] + pw * j;
            if(qp(a[i], a[i], pw * 10) == n % (pw * 10)) break;
        }
        pw *= 10;
    }
    cout << a[9] << endl;
}
signed main(){
    ios::sync_with_stdio(false);
    cin >> t;
    for(int i = 1; i < 100; i++) if(i % 2 && i % 5) f[qp(i, i, 100)] = i;
    while(t--) solve();
    return 0;
}