Задача "Обратные числа"

Question

Обратное число В этой задаче нужно ответить на 1≤t≤10^5 запросов. Каждый запрос состоит из двух целых чисел 2≤p≤10^9 и 0<a<p, число p является простым. На каждый запрос нужно вывести в отдельной строке целое число 0<b<p такое, что (a⋅b−1) ⋮ p.

Входные данные

В первой строке дано целое число t — количество запросов.

В следующих t строках даны по два числа pi и ai, i=1,…,t.

Выходные данные

Выведите t целых чисел (каждое число в отдельной строке) — ответы на запросы.

Примеры Ввод 4

5 1

5 2

5 3

5 4

Вывод 1

3

2

4

Вот мой код:

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
    unsigned long long _;
    cin >> _;
    for (unsigned long long t = 0; t < _; t++) {
        unsigned long long a, p;
        cin >> p >> a;
        unsigned long long ans = pow(a, p-2);
        cout << ans % p << '\n';
    }

    return 0;
}

Тестирующая система сообщает о неверном ответе.

Answer 1

Нужна функция возведения в степень, включающая в себя взятие модуля.

#include <cmath>

using namespace std;

unsigned long long modpow(unsigned long long base, unsigned long long exp, unsigned long long modulus) {
  base %= modulus;
  unsigned long long result = 1;
  while (exp > 0) {
    if (exp & 1) result = (result * base) % modulus;
    base = (base * base) % modulus;
    exp >>= 1;
  }
  return result;
}

int main()
{
    unsigned long long _;
    cin >> _;
    for (unsigned long long t = 0; t < _; t++) {
        unsigned long long a, p;
        cin >> p >> a;
        unsigned long long ans = modpow(a, p-2, p);
        cout << ans << '\n';
    }

    return 0;
}

БЛОГ НА HUSL

Задача "Обратные числа"

Ответы (1 шт):