Cod sursa(job #1540956)
Utilizator | Tudor Mocioi tgm000 | Data | 3 decembrie 2015 16:03:09 |
---|---|---|---|
Problema | Invers modular | Scor | 10 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.55 kb |
#include<cstdio>
int main(){
int a,n,d,p,cn;
long long phi,rez;
freopen("inversmodular.in","r",stdin);
freopen("inversmodular.out","w",stdout);
scanf("%d%d",&a,&n);
cn=n;
phi=n;
d=2;
while(d*d<=n){
if(n%d==0){
phi=(phi/d)*(d-1);
while(n%d==0)
n/=d;
}
d++;
}
if(n!=1)
phi=(phi/n)*(n-1);
p=phi-1;
rez=1;
n=cn;
while(p!=0){
if(p%2==1){
rez=(rez*a)%n;
p--;
}
else{
p/=2;
a=(a*a)%n;
}
}
printf("%d",rez);
return 0;
}