题解 P4139 【上帝与集合的正确用法】

andyli · 2020-02-07 22:27:28 · 题解

原题可转化为解方程2^x\equiv x(\text{mod}~ m)。
由欧拉定理得2^x\equiv 2^{x~\text{mod}~\varphi(m)+\varphi(m)} (\text{mod}~m)，那就转化为求x~\text{mod}~\varphi(m)。

递归求解，至m=1时终止即可。
可以证明递归的层数不大于2\log 2m。

代码如下（快读模板）：

const int maxn = 10000005;

int phi[maxn], r[maxn];
bool vis[maxn];
vector<int> primes;
void init(int n)
{
    phi[1] = 1;
    vis[0] = vis[1] = true;
    for (int i = 2; i <= n; i++) {
        if (!vis[i])
            primes.push_back(i), phi[i] = i - 1, r[i] = i;
        for (size_t j = 0; j < primes.size() && i * primes[j] <= n; j++) {
            vis[i * primes[j]] = true;
            r[i * primes[j]] = primes[j];
            phi[i * primes[j]] = phi[i] * (primes[j] - (primes[j] < r[i]));
            if (i % primes[j] == 0)
                break;
        }
    }
}
int quick_pow(int a, int n, int p)
{
    a %= p;
    int ans = 1;
    while (n) {
        if (n & 1)
            ans = 1LL * ans * a % p;
        a = 1LL * a * a % p;
        n >>= 1;
    }
    ans %= p;
    return ans;
}
int f(int p) { return p == 1 ? 0 : quick_pow(2, f(phi[p]) + phi[p], p); }
int main()
{
    init(maxn - 5);
    int T;
    io.read(T);
    while (T--) {
        int p;
        io.read(p);
        writeln(f(p));
    }
    return 0;
}