Cod sursa(job #3192927)
Utilizator | Dobra Emilia Emilia23 | Data | 13 ianuarie 2024 15:34:19 |
---|---|---|---|
Problema | Invers modular | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.62 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
long long MOD;
long long pow_log(long long x,long long n)
{
long long sol=1;
while(n)
{
if(n%2)sol*=x,sol%=MOD;
x*=x;
x%=MOD;
n/=2;
}
return sol;
}
int main()
{
long long a,n,phi;
f>>a>>n;
MOD=n;
phi=n;
for(int i=2;i*i<=n;i++)
if(n%i==0)
{
while(n%i==0)n/=i;
phi/=i;
phi*=(i-1);
}
if(n!=1)
{
phi/=n;
phi*=(n-1);
}
g<<pow_log(a,phi-1);
}