大きな乗算をするときにintオーバーフローを避ける

Question

プログラミングコンテストに参加するためのトレーニングをしていますので、そのような問題でよく慣れるようにしています。私は特に何かに問題を抱えてきました。驚くほど大きな数字のためにintがオーバーフローしました。この特定の問題が解決方法を知りたいと思います：Amelia and Rabbit Island。これは私のコードです：問題で

#include <iostream> 

int main(){ 

    unsigned long long int a,b,c; 
    int t; 

    int nweeks; 

    std::cin >> t; 

    int **lines = new int*[t]; 
    for (size_t i = 0;i<t;i++) 
     lines[i] = new int[3]; 

    for(size_t i=0;i<t;i++) 
     for(size_t j=0;j<3;j++) 
     std::cin >> lines[i][j]; 


    for (size_t i=0;i<t;i++){ 
     a = lines[i][1]; 
     b = lines[i][2]; 
     const unsigned int mod = 1000000; 
     for (size_t j=0;j<lines[i][0] - 2;j++){ 

     if (j > 0){ 
      c = a; 
      a = a * b % mod; 
      b = c; 

     } 
     else { 
      a = a * b; 
     } 
     } 

     nweeks = (lines[i][0] * 3) - 2; 

     std::cout << "At week " << nweeks << " we obtain " << a%mod << " new rabbits.\n"; 
    } 


    for (size_t i=0;i<t;i++) 
     delete[] lines[i]; 

    delete[] lines; 
    return 0; 
} 

それは、これはオーバーフローを避けることになっている、答えはMOD（1000000）で表現されなければならないことを言いますが、私はちょうどそれを動作させるための方法を見つけることができません、私の解決策は、正常値のために動作しますが、例えば入力の特定の場合：

1千10 10

単一の場合の最大許容入力されたことを、私が手に出力されます：

2998週で、我々は新たなウサギを0個得る。 どちらが間違っていますか？整数が乗算であふれているからです。

ありがとうございます。

編集：まあ、何らかの理由で、評価システムは今、miソリューション-.-を受け入れます。とにかく感謝します。

Answer 1

あなたは不幸な入力を選択しました。

あなたは

std::cout << "a: " << a << "\n"; 
std::cout << "b: " << b << "\n"; 

、forループの最後の行として出力aとbに数行を追加する場合は、aとb変更のどの値をトレースすることができます。入力として1 10 10 10を使用することにより

、私は次の出力を得る：その後

a: 100 
b: 10 
a: 1000 
b: 100 
a: 100000 
b: 1000 
a: 0 
b: 100000 
a: 0 
b: 0 
a: 0 
b: 0 
a: 0 
b: 0 
a: 0 
b: 0 
At week 28 we obtain 0 new rabbits. 

を、aとbはゼロであり続けるだろう。答えは間違っていません。出力モジュラス100000は実際にはゼロです。結果の両方のセットが正しいにもかかわらず、より受け入れ見える

a: 64 
b: 8 
a: 512 
b: 64 
a: 32768 
b: 512 
a: 777216 
b: 32768 
a: 813888 
b: 777216 
a: 775808 
b: 813888 
a: 821504 
b: 775808 
a: 375232 
b: 821504 
At week 28 we obtain 375232 new rabbits. 

：入力として1 10 8 8を使用することにより

、私は次の出力を取得します。