Çarpımın üzerine taşması C++

Question

Kodumda iki sayıyı çarpmaya çalışıyorum. Algoritma basittir (k) * (k-1)^nI değişkeni (k-1)^n değişken p1'de ve sonra n = 10 ile çarpın, k = 10 (k-1)^n-1 387420489 olmalı ve bunu p1 değişkeniyle aldım ama k ile çarparak negatif bir sayı elde ediyorum. 3874208490 yerine, başka büyük pozitif bir sayı elde ediyorum. Doğru yaklaşım nedir?

#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 türünde nedir? Eğer sadece int ise (ve eminim ki), taşma yapar, çünkü 32 bit imzalı tip yaklaşık 2 * 10^9'a eşit olan (2^31) -1'den daha fazla değer depolayamaz. Çalışmasını sağlamak için long long int'u kullanabilirsiniz, daha sonra kodunuz 2^63'den daha düşük sonuçlarla çalışacaktır.

Answer 2

Bir taşma elde etmeniz şaşırtıcı değil. Ben, çok hızlı bir şekilde k çevresinde = 80.

10^21 70 ikili bit çok dikey gerektirir alır az 10, n, sabitleme ve 0 ila 100

eğrisi için k yineleme, volfram alfa denkleminizi takılı onu temsil etmek için, ve sadece uzun bir süre 63 var.

Bu algoritmanın parametrelerinin sınırlarının ne olduğuna karar vermeniz ve karşılık gelen veri türlerini seçmeniz gerekecek. Belki bir çift daha uygun olur?

link to plot is here