Cod sursa(job #815579)
Utilizator | Ungureanu Mihnea UMihnea | Data | 17 noiembrie 2012 11:06:59 |
---|---|---|---|
Problema | Invers modular | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.63 kb |
#include <cstdio>
using namespace std;
long long n,m,p,e,a,sol;
int main()
{
freopen("inversmodular.in","r",stdin);
freopen("inversmodular.out","w",stdout);
scanf("%lld%lld",&a,&n);
m=n;
e=1;
for(p=2;p*p<=n;p++)
if(n%p==0)
{
while(n%p==0)
{
n/=p;
e*=p;
}
e/=p;
e*=p-1;
}
if(n>1)e*=n-1;e--;
sol=1;
for(;e;e/=2)
{
if(e%2==1)
sol=(sol*a)%m;
a=(a*a)%m;
}
printf("%lld",sol);
return 0;
}