如何计算 a^b^c mod p？

Question

我正在尝试为一些正整数 a、b、c、p 计算 a^b^c mod p。一种可能的（也是显而易见的）方法是使用快速 mod 平方求幂，它将运行 in O(log(b^c))=clog(b)。虽然我不介意这里的效率，但这种方法的明显缺点是您需要 b^c 的显式二进制表示，它本身已经是指数的。

所以我的问题是，如果我不能将 b^c 表示为二进制表示，有没有一种方法可以从二进制表示中计算 a^b^c mod p a,b, and c?

Answer 1

(a^b^c) mod p = (((a^b) mod p)^c) mod p

所以你可以做到

modpow(modpow(a,b,p),c,p);

其中所有操作数结果和子结果都是普通整数。作为 modpow，您可以通过模 p 的平方来使用幂，如下所示：

Modular arithmetics and NTT (finite field DFT) optimizations

注意那些利用特定选择的属性进行了一些优化p所以你需要像

这样改变行

if (DWORD(d)>=DWORD(p)) d-=p;

进入

d%=p;

[示例]

(2^3^5) % 6 = 
(8  ^5) % 6 =
  32768 % 6 = 2

(((2^3)%6)^5) % 6 = 
((   8 %6)^5) % 6 = 
(    2    ^5) % 6 =
    32        % 6 = 2

Answer 2

https://discuss.codechef.com/t/compute-a-b-c-mod-p/1989 在解决 https://cses.fi/problemset/task/1712 之后检查此页面。上面的回答 modpow(modpow(a,b,p),c,p); 看起来很合乎逻辑，但它不会工作（你可以通过上面提到的CSES问题来验证它）。使用这个 formula/method modpow(a,modpow(b,c,p-1),p); 。他们使用费马定理推导出这个 modpow(a,modpow(b,c,p-1),p); 。顺便说一下cpp代码如下：

#include <bits/stdc++.h>
#define ar array
#define int long long
using namespace std;

const int mxN=2e5+2,mxM=1003,M=1e9+7;

int pM(int n,int p,int M)
{
    int res=1;
    while(p)
    {
        if(p&1)
            res=res*n%M;
        n=n*n%M;
        p>>=1;
    }
    return res;
}
signed main()
{
    int t;
    cin>>t;
    while(t--)
    {
         int a,b,c;
        cin>>a>>b>>c;
        cout<<pM(a,pM(b,c,M-1),M)<<"\n";
    }

    return 0;
}

如何计算 a^b^c mod p？

How to compute a^b^c mod p?

math

modulo

exponentiation

mod