3

Обратное число

В этой задаче нужно ответить на 1≤t≤105 запросов. Каждый запрос состоит из двух целых чисел 2≤p≤109 и 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

cpp

#include <cmath>
using namespace std;
int pow_plus(int a, int b){
    int z = pow(b, a - 2);
    return z % a;
}

int main()
{
    int n;
    int a,b;
    cin >> n;
    int mas[n];
    for(int i = 0; i < n; i++){
        cin >> a;
        cin >> b;
        mas[i] = pow_plus(a,b);
    }

    for(int i = 0; i < n; i++){

        cout << mas[i];
        if(i + 1 != n){
            cout <<'\n';
        }
    }



    setlocale(LC_ALL, "rus");
    return 0;

}

Вердикт: Неверный ответ, почему не работает?

4
  • 1
    int z = pow(b, a - 2); - переполнение. 19 июл 2021 в 21:21
  • В С++ это cin >> n; int mas[n]; не работает. n должна быть константой. Если размер массива хочется вводить, то используйте std::vector. Ну или простой динамический массив.
    – Vladimir
    19 июл 2021 в 22:39
  • @Vladimir В данном случае проблема не в этом (обычно во всех проверялках GCC, а у него это работает).
    – Harry
    20 июл 2021 в 4:37
  • Быстрое возведение в степень + взятие остатка помогут. И давайте в таких случаях URL проверяющей системы! P.S. А вы хоть знаете, почему решение именно такое?
    – Harry
    20 июл 2021 в 4:37

1 ответ 1

4

В комментарий не лезет...

Вот, как-то набрасывал для себя такую функцию - возведения в степень по модулю...

//// Быстрое возведение в степень по модулю p
template<typename T, typename U, typename P,
         typename = std::enable_if_t<std::is_integral<T>::value &&
                                     std::is_unsigned<P>::value &&
                                     std::is_unsigned<U>::value>
        >
T iqpow(T x, U e, P p)
{
    T res = static_cast<T>(1);
    x %= p;
    for(;e;e>>=1)
    {
        if (e&1) res = (res*x)%p;
        x = (x*x)%p;
    }
    return res;
}

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.