9

我想编写计算 pow(a,b)%MOD 值的代码。我使用 C++ 编写代码。

但问题是 b 的值可能非常大。我知道 log(b) 时间复杂度方法。但是，b 的值可能不适合 C++ 的“long long”数据类型。例如 b 可以是第 1000000000 个斐波那契数。如此大的数字的精确计算本身是不可能的（在时间限制内）。

PS：

  • pow(a,b) 表示 a*a*a*a*... b 次。
  • X % MOD 是指 X 除以 MOD 所得的余数。
4

7 回答 7

13

这是一个典型的任务。请（或者，真的，请！）阅读有关Euler 的 totient 函数的信息。

然后是欧拉定理。

问题是您可以将 a^b 大幅减少到 a^(b % phi(MOD))。是的，您将需要某种整数分解方法，但仍然没有关于实际计算所需功率的疯狂想法。

在我年轻的时候，我们手工制作了这样的样本 :) 即使数字远远超出 32/64 位范围。

编辑：嗯，你生活和学习。2008年获得的结果是：

“totient 是 gcd 的离散傅立叶变换：(Schramm (2008))”

所以计算 phi(b) 不需要知道它的因数。

编辑（2）：

Carmichael 函数是您需要计算得到任何 a、b 和 MOD 的正确答案的函数。

于 2012-06-30T08:15:45.387 回答
3

我用这个功能来解决这个问题

UVA 374 - 大模组

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=310

// a^b % T

// with Exponentiation by squaring (http://en.wikipedia.org/wiki/Exponentiation_by_squaring#Basic_method)

// if a very large use
// R=(unsigned long long)(R*a)%T;

int restOfPot(long long a,int b,int T)
{
    a%=T;
    long long R=1;

    while(b)
    {
        if(b&1) R=(R*a)%T;
        a=(a*a)%T;
        b>>=1;
    }

    return int(R);
}
于 2014-10-09T15:56:48.393 回答
1

要处理非常大的数字，请查看boost 的 Multiprecision库。它有一个 powm() 函数可以很好地用于此目的。

来自泛型整数运算：</p> 

template <class Integer>
Integer powm(const Integer& b, const Integer& p, const Integer& m);

返回 b p % m。

例子：

#include <boost/multiprecision/cpp_int.hpp>

boost::multiprecision::cpp_int pow("8912627233012800753578052027888001981");
boost::multiprecision::cpp_int mod("0x86f71688cdd2612c117d1f54bdae029");
boost::multiprecision::cpp_int base(12345);

boost::multiprecision::cpp_int result = powm(base, pow, mod);

std::cout << "result is: " << result << std::endl;

印刷：

result is: 5758534182572671080415167723795472693
于 2014-01-21T08:22:31.637 回答
0

首先：^在 C/C++ 中不是幂的运算符。事实上，没有运营商可以做到这一点。^表示按位XOR。您必须使用pow(base, exp)可以在标题math.h或cmath.

对于如此庞大的数字，使用double或long double（确切的长度和生成的数据类型可能因您的平台而异），但有时您会偶然发现精度问题，因此根据您的用例，您最好的选择可能是使用的值的大小自定义数据类型（编辑：例如来自链接问题之一中的库之一）。

于 2012-06-30T07:56:22.920 回答
0

我建议使用专门的数学库。这看起来也像加密，所以我建议使用加密库。GNU 一定有一个你可以使用的。这是因为在加密货币中，在许多情况下，可能会选择指数以使用普通数学库无法假设的快捷方式进行有效计算。

于 2012-06-30T07:59:24.417 回答
0

但是，b 的值可能不适合 C++ 的“long long”数据类型。例如 b 可以是第 1000000000 个斐波那契数。

对于这样的事情，有一个简单的解决方法：召回

a^(b+c) == a^b * a^c mod d

您可以使用与计算斐波那契数相同的递归来计算您询问的特定产品——您根本不需要大数或模幂！

有时出现的另一个版本是

a^(b*c) = (a^b)^c mod d

于 2015-05-09T09:48:51.097 回答
0 
#include<bits/stdc++.h>
using namespace std;

#define mod 1000000007
#define ll long long

ll power(ll x, ll y)
{
    if ( y == 0)
        return 1;
    ll temp = power(x, y / 2);
    if (y % 2 == 0)
        return (temp * temp) % mod;
    else
        return (((temp * temp) % mod) * x) % mod;
}
ll dmod(ll x)
{  
    return ((x + mod) % mod);
}

ll modular_power(ll x, ll y)
{
    ll ans = 1;
    while (y)
    {
        if (y & 1)ans = dmod(ans * x);
        y /= 2;
        x = dmod(x * x);
    }
    return ans;
}

int main()
{ 
    ll a, b;
    cin >> a >> b;
    ll ans1 = modular_power(a, b);
    ll ans2 = power(a, b);
    //  both answers are same
    cout << ans1 << " " << ans2 ;
}
于 2021-06-24T07:17:09.737 回答