大量增加功率并大量修改？ [英] Raising large number to large power and mod it by a large number?

问题描述

我可能会遇到一个简单的问题。
我有3个大数（A，B，C），所有整数，我需要执行以下操作：将A乘以B，然后将结果乘以C，然后检查结果是否等于1。我的代码：

I am stuck with probably simple question. I got 3 large numbers(A,B,C), all integers and i need to do the following: power A to B and modulo the result by C, and then check if the result is equal to 1. Here's my code:

double power = fmod((pow((double)A,(double)B)),(double)C);
    if (power != 1){
        printf("Something!\n");
    }

而且它不起作用（我尝试了小数，例如17由28和由29个模块）。对此有任何建议吗？

And it doesnt work(I tried small numbers, like 17 powered by 28 and moduled by 29). Any suggestions on that?

推荐答案

尝试一下（为了避免算术溢出）：

Try this (in order to avoid arithmetic overflow):

unsigned long long power = 1;
A %= C;
while (B > 0)
{
    power = (power * A) % C;
    B--;
}

您可以通过以下方式进一步提高运行时性能：

You can further improve the runtime performance with this:

unsigned long long power = 1;
A %= C;
while (B > 0)
{
    if (B & 1)
        power = (power * A) % C;
    B >>= 1;
    A = (A * A) % C;
}

这篇关于大量增加功率并大量修改？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！