Cod sursa(job #2467827)
Utilizator | Data | 5 octombrie 2019 08:52:07 | |
---|---|---|---|
Problema | Invers modular | Scor | 0 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.7 kb |
#include <bits/stdc++.h>
using namespace std;
int Phi(int n)
{
int sol = n, p;
for(p=2;p*p<=n && n>1;p++)
{
if(n%p==0)
sol=sol/p * (p-1);
while (n%p==0)
n/=p;
}
if(n>1)
sol=sol/n * (n-1);
return sol;
}
int LogP(int a,int n, int mod)
{
int p=1;
while(n>0)
{
if(n%2==1)
p=1LL*p*a%mod;
n/=2;
a=a*a%mod;
}
return p;
}
int main()
{
int a,n,phi;
ifstream fin("inversmodular.in");
ofstream fout("inversmodular.out");
fin>>a>>n;
phi=Phi(n);
fout<< LogP(a,phi-1,n) <<"/n";
fin.close();
fout.close();
}