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

-3

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?Çarpımın üzerine taşması C++

#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; 
    } 
}

kaynak

2016-04-05 satyajeet jha

doğru girinti – MIbrah

kullanın 'i modulous' kullanılan - bir yazım denetimi kullanabilir ve modül daha sık. – greybeard

Ne yazık ki bu satya gününde sıçrama gibi görünüyor. Makro veya yazım denetimi yapıp, kodunuzu neredeyse erişilemez duruma getirdiniz. Yazılım geliştirme alanında bir kariyer planladığınızda kötü bir fikirdir ve bir kod gizleme yarışmasında kazanmak istiyorsanız daha fazla çaba göstermeniz gerekir. – user4581301

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.

kaynak

2016-04-05 21:45:52 Victor

Uzun uzun 'bir typedef olduğunu varsayalım. –

@Victor uzun uzun –

@satya bu tür kontrol ile 10 000 000 000 numarasını okuyabilir ve daha sonra yazabilirsiniz. 32-bit imzalı olduğu gibi davranır. – Victor

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

kaynak

2016-04-05 23:10:57

cevap

İlgili konular