如何计算 a^b^c mod p

Question

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

所以对我来说的问题是，如果我不能将b^c表示为二进制表示，有没有办法从a,b, and c的二进制表示中计算出a^b^c mod p？

Answer 1

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

所以你可以做

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

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

• 模块化算法和NTT（有限域DFT）优化

请注意，这些是利用特定选定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问题进行验证）。使用此公式/方法 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;
}