Oveflow, даже если int мод на 10 ^ 9 + 7

Question

Я написал следующий код для факториала числа:

long int fac[max+1];
    fac[0]=1;


    for(int j=1;j<=max;j++)
        {
            fac[j]=(fac[j-1]*j)%1000000007;
        }


    //Printing
    for(int i=0;i<T;i++)
        {
            cout<<fac[N[i]]<<"\n";
        }

Это прекрасно работает для long int, но мы получим неправильный ответ, если мы изменим массив на int.

Скажите, пожалуйста, почему это происходит, когда диапазон значений int больше 10 ^ 9 + 7.

Answer 1

Мы знаем, что 0 ≤ fac[j - 1] <10 <sup>9 + 7. Но fac[j - 1] * j будет в j раз больше, а long иногда имеет длину только 32 бита(Windows).Абсолютное максимальное значение, которое вы можете вписать в 32-битное число, равно 4294967295, только примерно в четыре раза больше вашего модуля.

Рассмотрите возможность использования unsigned long long вместо long int - это должно работать до j> 2 ³⁴ .

Фактически, учитывая, что (a * b) % N математически эквивалентно - (a % N) * (b % N), после замены long int на unsigned long long Вы можете переписать

fac[j] = (fac[j - 1] * j) % 1000000007

в

fac[j] = (fac[j - 1] * (j % 1000000007)) % 1000000007

Тогда, поскольку 1000000007 ² <2 <sup>64 , вы должны быть в состояниипродолжайте это вечно (хотя, конечно, вам не хватит места для fac).

Answer 2

с int fac[max+1];, fac[j-1] * j равно int * int с результатами в int.

если вы переполнены, у вас есть UB и даже с неподписанным, вы потеряете данные.

с long int fac[max+1];, тогда fac[j-1] * j равно long int * long int (int -> long int для j) с результатами в long int.