题解 - ARC172E

Jian_Yu · 2024-02-19 16:43:09 · 题解

题目链接

讲一种比较暴力的做法。

写一个暴力随便尝试几个数，容易发现对于一个数 x，当 y\ge2 且 x 与 10 互质时，有

具体证明可以看这里。

而我们发现题目中刚好保证了 x 与 10 互质，所以我们只需要取 y\ge2 即可

于是可以直接预处理出 1\sim10^6 中每个数 x 的 x^x\bmod10^6 的值，然后每次询问时查表可以得到后六位，接下来只需要枚举前三位逐一判定即可。

全部跑满大概是 10^6\log10^6+10^4\times10^3\log10^9 也就是 4\times10^8 次运算，实际跑不满，所以卡卡常就能通过。

具体代码实现非常的简单。

#include <iostream>
using namespace std;
const int MOD = 1e9;
typedef long long ll;
const int M = 1e6, K = 1e3;
ll qpow(ll x, int k){
    ll res = 1;
    for(; k; k >>= 1, x = x * x % MOD)
        if(k & 1) res = res * x % MOD;
    return res;
}

ll q, x;
int v[M+50];
int main(){
    for(int i = 1; i <= M; ++i){
        int val = qpow(i, i);
      v[val % M] = i;
    } 
    for(cin >> q; q--; ){
        cin >> x;
        int pre = v[x%M];
        for(int j = 0; j < K; ++j){
            int nxt = j * M + pre;
            if(qpow(nxt, nxt) == x){
                cout << nxt << "\n";
                break;
            }
        }
    }
}