BZOJ3884 上帝与集合的正确用法

2015.02.26 16:15 Thu| 10 visits oi_2015| 2015_刷题日常| Text

Solution

orz PoPoQQQ 出题人官方题解。为什么原题解是图片格式?一定是他的博客系统太渣了 →_→

令 $p = 2^k * q$,其中 $q$ 是一个奇数,那么我们有:

$2^{2^{2^{2^\cdots}}} \mod p = 2^k(2^{2^{2^{2^\cdots}}-k}\mod q)$

由于 $q$ 是奇数,故 $q$ 与 $2$ 互质,可以套用欧拉定理:

$2^k·2^{2^{2^{2^\cdots}}-k}\equiv2^k·2^{(2^{2^{2^\cdots}}-k)\mod \varphi(q)}\mod q$

指数上是和一开始的式子同样的形式,可以递归做下去。

容易发现除第一次外模数都是偶数,故每次递归模数都会至少除掉2。因此在不超过 $\mathcal O(\log_2p)$ 次递归之后,模数就会变成1。由于任何数 $\mod 1$ 的结果都是 $0$,故此时递归结束,回溯并计算结果即可。

如果使用线性筛计算欧拉函数,时间复杂度 $\mathcal O(p+T\log_2p)$。

如果每次 $\mathcal O(\sqrt p)$ 计算欧拉函数,时间复杂度 $\mathcal O(T\log_2p\sqrt p)$,实践中后者速度完爆前者。

如果通过递推的方式依次计算 $\mod 1 → \mod 1000W$ 的值,时间复杂度为 $\mathcal O(p)$,由于常数太大实测TLE。

由于出题人代码的常数太大,实测没进第一篇。

在此致敬 28ms 的大神们。40ms,我尽力了。

Code

#include <bits/stdc++.h>
using namespace std;

inline int read()
{
    int x = 0, f = 1; char ch = getchar();
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = x * 10 + ch - '0'; ch = getchar(); }
    return x * f;
}

int power(int a, int b, int p)
{
    int re = 1;
    while (b)
    {
        if (b & 1) re = 1ll * re * a % p;
        a = 1ll * a * a % p; b >>= 1;
    }
    return re;
}

int phi(int n)
{
    int re = n;
    for (int i = 2; i * i <= n; ++i)
    {
        if (n % i == 0) re = re / i * (i - 1);
        while (n % i == 0) n /= i;
    }
    if (n != 1) re = re / n * (n - 1);
    return re;
}

int getans(int p)
{
    if (p <= 1) return 0;
    int k = 0;
    while ((p & 1) == 0) p >>= 1, ++k;
    int t = phi(p), re = getans(t);
    return (power(2, ((re - k) % t + t) % t, p) % p) << k;
}

int main()
{
    int t = read();
    while (t--)
        printf("%d\n", getans(read()));
}