Cod sursa(job #2292982)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 30 noiembrie 2018 12:58:05
Problema Invers modular Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.89 kb
#include <fstream>

using namespace std;

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

int A, N;

int GetPhi(int x)
{
    int ans = x, xx = x;

    if(x % 2 == 0)
    {
        ans /= 2;
        while(x % 2 == 0)
            x /= 2;
    }

    for(int i = 3; i * i <= xx; i += 2)
        if(xx % i == 0)
        {
            ans = (ans / i) * (i - 1);

            while(x % i == 0)
                x /= i;
        }

    if(x)
        ans = (ans / x) * (x - 1);

    return ans;
}

int Power(int base, int exp)
{
    int sol = 1;
    int aux = base;

    for(int i = 1; i <= exp; i <<= 1)
    {
        if(i & exp)
            sol = 1LL * sol * aux % N;

        aux = 1LL * aux * aux % N;
    }

    return sol;
}

int main()
{
    fin >> A >> N;

    int phi = GetPhi(N);
    fout << Power(A, phi - 1);

    return 0;
}