C++の乗算でオーバーフローが発生する

Question

私のコードでは、2つの数値を掛けようとしています。アルゴリズムは、（p-1）^ nを変数p1に格納してから私はk = 10で、k = 10（k-1）^ n-1は387420489でなければならず、これは変数p1で得られますが、kと掛け合わせると負の数になります。 3874208490の代わりに、私は他の大きな正の数を取得します。正しいアプローチは何ですか？

#include <iostream> 

using namespace std; 

typedef long long ll; 

ll big = 1000000000 + 7; 

ll multiply(ll a, ll b) 
{ 
    ll ans = 1; 
    for (int i = 1; i <= b; i++) 
     ans = ans * a; 
    return ans % big; 
} 

int main() 
{ 
    int t; 
    scanf("%d", &t); 
    while (t--) 
    { 
     ll n, k; 
     cin >> n >> k; 
     ll p1 = multiply(k - 1, n - 1); 
     cout << p1 << endl; // this gives correct value 
     ll p2 = (k % big) * (p1 % big); 
     cout << ((p2 + big) % big) % big << endl; 
    } 
} 

Answer 1

llとは何ですか？それはちょうどint（と私はかなり確信している）、それは32ビットの符号付きタイプは2 * 10^9にほぼ等しい（2^31）-1以上の値を格納することはできませんので、オーバーフローします。 long long intを使用すると、コードは2^63未満の結果で動作します。

Answer 2

オーバーフローが発生するのは驚くことではありません。私は、曲線の周りのk = 80

10^21で非常に速く、非常に垂直なり、タングステンアルファにあなたの式を差し込む10にNを固定し、0から100

にKを反復する70進ビットを必要としますそれを表現するためには、あなたは長く長い間63しか持っていません。

このアルゴリズムのパラメータの制限と、対応するデータ型の選択を決める必要があります。おそらくダブルがより適しているでしょうか？

link to plot is here