Почему программа не работает?

Question

[Алескей Дворяшин]

Задача:


Мое решение:

#include <iostream>

using namespace std;
int fast_deg(int a, int deg) {
    if (deg == 1) {
        return a;
    }
    if (deg % 2 == 0) {
        return fast_deg(a, deg / 2) * fast_deg(a, deg/2);
    }
    return a * fast_deg(a, deg / 2) * fast_deg(a, deg/2);
}
int main()
{
    int t, p, a;
    
    cin >> t;
    for (int i = 0; i < t; i++) {
        cin >> p >> a;
        cout << fast_deg(a, p - 2) % p<< "\n";
    }

    return 0;
}

Ошибку исполнения выдаёт во втором тесте, а сам курс таков, что ты не можешь посмотреть ошибку (и входные данные, соответственно, тоже). Кучу раз тестил, ошибку поймать не смог. Где я ошибся?

Answer 1

[Wataru]

Проблема в том, что сначала пытаетесь вычислить a^(p-2), а потом взять его по модулю. В задаче числа до 10^9 и если вы попытаетесь вычислить что-то вроде 99999^1000005, то у вас int переменная переполнится, потому что там должны быть миллионы знаков в числе, а в int едва 10 влезает.

Надо брать по модулю при каждом умножении в возведении в степень.

Потому что (a*b)%p = (a%p)*(b%p) % p.

Edit:

Еще две ошибки: считать произведение надо в long long, потму что 10^9*10^9 в int не влезает.
И fast_deg(a, deg/2) надо вызывать только один раз, а то у вас функция работает за O(n) вместо O(log n).

Answer 2

[Rsa97]

Элементарно. fast_deg - это же быстрое возведение в степень.
Попробуйте посчитать, например, 27644436^27644437, оставаясь в рамках целых чисел C++.
Здесь надо использовать возведение в степень по модулю и правильно выбирать размер переменных.