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

それは典型的なタスクです。オイラーの totient 関数について読んでください (または、本当にお願いします!) 。

そしてオイラーの定理。

問題は、a^b を a^(b % phi(MOD)) に劇的に減らすことができるということです。はい、ある種の整数因数分解法が必要になりますが、実際に必要なべき乗を計算するというクレイジーなアイデアはありません。

私は若い頃、そのようなサンプルを手作業で行いました:) 32/64ビット範囲をはるかに超える数値の場合でも。

編集:まあ、あなたは生きて学びます。2008 年の結果は次のとおりです。

「totient は gcd の離散フーリエ変換です: (Schramm (2008))」

したがって、phi(b) を計算するために、その因数を知る必要はありません。

編集(2):

カーマイケル関数は、a、b、および MOD の正しい答えを得るために計算する必要があるものです。

于 2012-06-30T08:15:45.387 に答える
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

専用の数学ライブラリを使用することをお勧めします。また、これは暗号のように見えるので、暗号ライブラリを使用することをお勧めします。GNU には、必ず使用できるものがあります。これは、多くの場合、暗号では、通常の数学ライブラリが想定できないショートカットを使用して効率的な計算を行うために指数が選択される可能性があるためです。

于 2012-06-30T07:59:24.417 に答える
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 に答える
0

まず^、C/C++ ではべき乗の演算子ではありません。実際、これには演算子はありません。ビットごとのXOR^を表します。ヘッダーまたはにある whichを使用する必要があります。pow(base, exp)math.hcmath

このような巨大な数の場合、doubleor long double(正確な長さと結果のデータ型はプラットフォームによって異なる場合があります) を使用しますが、精度の問題に遭遇することがあります。カスタムデータ型（編集：リンクされた質問の1つにあるライブラリの1つから）。

于 2012-06-30T07:56:22.920 に答える