BZOJ 3884——欧拉降幂和广义欧拉降幂

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

理论部分

欧拉定理：若 $a,n$ 为正整数，且 $a,n$ 互质，则 $a^{\varphi (n)} \equiv 1(mod \ n)$.

降幂公式：

$$a^b=
\begin{cases}
a^{b \% \varphi(p)} & gcd(a,p)=1 \\
a^b & gcd(a,p)\neq 1,b < \varphi (p) \\
a^{b\% \varphi (p) + \varphi (p)} & gcd(a,p)\neq 1,b \geq \varphi (p)
\end{cases}$$

题目

求 $2^{2^{2...}} \ mod \ p$ 的值，$T$组询问。$T \leq 1000, p \leq {10}^7$

分析：

首先，必须明确模意义下的无穷与真正的无穷是有区别的，（不然无穷的怎么求值

由降幂公式，当 $x \geq \varphi (p)$ 时（这道题中 $x$ 一直为2的无穷次方，肯定大于 $\varphi(p)$），

$$a^x \equiv a^{x \% \phi (p) + \varphi (p)}(mod \ p)$$

所以，令 $f(p) = 2^{2^{2...}}(mod \ p)$，$f(1)=0$，

$$\\f(p)=2^{(2^{2^{...}} mod \; \phi(p)) + \phi(p)}mod \; p \\=2^{f(\phi(p)) + \phi(p)} mod \ p$$

因此可以递归求解。

时间复杂度是多少呢？

求 $\phi(p)$ 是 $\sqrt p$，进行 $\varphi (\varphi (...\varphi (p))) = O(logp)$ 次，直至为1，

所以总的复杂度为 $O(\sqrt p log p)$

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int p;

ll qpow(ll a, ll b, ll p)

{

    ll ret = ;

    while(b)

    {

        if(b&) ret = ret*a%p;

        a = a*a%p;

        b >>= ;

    }

    return ret;

}

int euler_phi(int n)

{

    int m = (int)sqrt(n + 0.5);

    int ans = n;

    for (int i = ; i <= m; i++)

    {

        if (n % i == )

        {

            ans = ans / i * (i - );

            while (n % i == )  n /= i;        //除尽

        }

    }

    if (n > )  ans = ans / n * (n - );    //剩下的不为1,也是素数

    return ans;

}

int f(int p)

{

    if(p == )  return ;

    int phip = euler_phi(p);

    return qpow(, f(phip)+phip, p);

}

int main()

{

    int T;

    scanf("%d", &T);

    while(T--)

    {

        scanf("%d", &p);

        printf("%d\n", f(p));

    }

    return ;

}