我已经成功地尝试了像 9^(10^9) 这样的数字的大 mod 算法。但是当功率也太大无法使用时，如何得到最终答案？
#include <iostream>
#include <cmath>
#define ULL unsigned long long
using namespace std;
ULL mod(ULL b, ULL p,ULL m)
{
ULL md=1,c;
while(p!=0)
{
if (p % 2 == 0)
{
md*=(b%m)*(b%m);
p=p/2;
}
else
{
md*=(b % m);
p--;
}
}
return md;
}
int main()
{
ULL b=4, p, m=pow(9,9), num,res;
cin >> p;
num= mod(b,p,m);
res=pow(num,4);
cout << res;
}
考虑计算 (4^(p))%(9^9) 的一般情况，其中 p 是一个大数(在本例中为 p = 4^(10^9))。考虑 4 模 9^9 的幂序列：(4^0)%(9^9) == 1， (4^1)%(9^9) == 4， (4^2)%(9^9) == 16，最终经过t个(t 未知)循环后，序列将循环回 (4^t)%(9^9) == 1，之后重复。(请注意，数字必须是"互质数"，否则经过一定数量的循环后，结果变为零并保持为零。因此，计算可以使用 p%t 而不是 p：
(4^(p))%(9^9) == (4^(p%t))%(9^9)
这看起来很大，但 t 将是 <= 9^9,9^9 <2^29,4 * 2^29 = 2^31，所以 64 位整数(需要平方以加速幂)将足够大来解决这个问题。所以现在的问题是解决t。您可以通过从 |m = 1 |t = 0 |然后循环使用 |m = (m*4)%(9^9) |t += 1 |直到 m == 1 再次。
例如，假设您正在寻找 t，以便：
(4^(p))%9 == (4^(p%t))%9
对于这个更简单的示例：
(4^0)%9 == 1 ;m == 1, t == 0
(4^1)%9 == 4 ;m == 4, t == 1
(4^2)%9 == 7 ;m == 7, t == 2
(4^3)%9 == 1 ;m == 1, t == 3 (end of loop)
所以 t == 3(对于这个更简单的情况)：
(4^(p))%9 == (4^(p%3))%9
正如DAle所评论的那样，还有与totient相关的欧拉定理：
https://en.wikipedia.org/wiki/Euler%27s_totient_function#Euler.27s_theorem
如果 a 和 n 是互质，则
(a^(ϕ(n)))%n = 1, where ϕ(n) is the totient function.
维基文章还包括一个函数的公式。
https://en.wikipedia.org/wiki/Euler%27s_totient_function#Euler.27s_product_formula
您可以使用 t = φ(9^9)。这不是满足 (4^(t))%(9^9) = 1 的最小值 t，但它已经足够好了。
问题发布已经两天了，所以继续
t = φ(9^9) = φ(3^18) = (3^18)(1-1/3) = 2(3^17) = 258280326
使用 loop 方法查找较小的值，t = 3^17 = 129140163。然后用于内部功率模数
p%t = ( (4^(10^9)) % 129140163 ) = 19457986
然后继续外部功率模数的过程
(4^(4^(10^9)))%(9%9) = (4^19457986)%(9^9) = 335228719
示例代码：
#include <stdio.h>
typedef unsigned long long uint64_t;
/* count number of cycles t such that */
/* (v^t)%m = 1 */
uint64_t cntcyc(uint64_t v, uint64_t m)
{
uint64_t t = 0;
uint64_t i = 1;
do {
i = (i * v) % m;
t++;
} while (i != 1);
return t;
}
/* v to power p modulo m */
uint64_t powmod(uint64_t v, uint64_t p, uint64_t m)
{
uint64_t s = v; /* repeated square */
uint64_t r = 1; /* result */
while(p){
if(p&1)
r = (r*s)%m;
s = (s*s)%m;
p >>= 1;
}
return r;
}
int main()
{
uint64_t r;
r = cntcyc(4ull, 387420489ull); /* 4, 9^9 */
printf("%llun", r); /* 129140163 */
r = powmod(4ull, 1000000000ull, r); /* (4^(10^9))%r */
printf("%llun", r); /* 19457986 */
r = powmod(4ull, r, 387420489ull); /* (4^r)%(9^9) */
printf("%llun", r); /* 335228719 */
r = 258280326ull; /* r = totient(9^9) */
r = powmod(4ull, 1000000000ull, r); /* (4^(10^9))%r */
printf("%llun", r); /* 19457986 */
r = powmod(4ull, r, 387420489ull); /* (4^r)%(9^9) */
printf("%llun", r); /* 335228719 */
r = 258280326ull; /* r = totient(9^9) */
r = powmod(4ull, 1000000000ull, r); /* (4^(10^9))%r */
/* show that r += 3^17 doesn't effect final result */
r += 129140163ull; /* r += 3^17 */
printf("%llun", r); /* 148598149 */
r = powmod(4ull, r, 387420489ull); /* (4^r)%(9^9) */
printf("%llun", r); /* 335228719 */
return 0;
}