Cod sursa(job #2029750)

Utilizator ezioconnorVlad - Gabriel Iftimescu ezioconnor Data 30 septembrie 2017 13:22:54
Problema Invers modular Scor 60
Compilator cpp Status done
Runda Arhiva educationala Marime 0.48 kb
#include <iostream>
#include <fstream>

using namespace std;
using i64 = long long;

ifstream in("inversmodular.in");
ofstream out("inversmodular.out");

i64 a, n;

i64 expow(i64 b, i64 e, i64 mod)
{
    i64 ans = 1;
    for (int bit = 0; (1ll << bit) <= e; ++bit)
    {
        if (e & (1ll << bit))
            ans = ans * b % mod;
        b = b * b % mod;
    }
    return ans;
}

int main()
{
    in >> a >> n;
    out << expow(a, (n - 2), n);
    return 0;
}