如何有效地验证pow(a,b)%b==C中的a(无溢出)

您可以使用 Exponentiation by squaring

其思路如下:

• b 以二进制形式并分解乘积
• %b 低于32768,因此结果将始终适合32位数字。

所以C代码是:

/*
 * this function computes (num ** pow) % mod
 */
int pow_mod(int num, int pow, int mod)
{
    int res = 1

    while (pow>0)
    {
        if (pow & 1)
        {
            res = (res*num) % mod;
        }
        pow /= 2;
        num = (num*num)%mod;
    }

    return res;
}

你在做Z/bZ中的模算术。

(a^b) mod b = ((((a mod b) * a) mod b) * a) mod b [...] (b times)

因此,您不需要一个大的整数库。

您只需使用以下算法(伪代码)编写一个C程序:

• 将变量a和b声明为整数。
• 使用用a初始化的临时变量temp。
• 用b步做一个循环,然后计算 (temp * a) mod b

通过这个公式,可以看到temp的最高值是32768,因此可以选择一个 存储温度。