Cod sursa(job #2123697)
Utilizator | Data | 6 februarie 2018 15:41:30 | |
---|---|---|---|
Problema | Invers modular | Scor | 10 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.59 kb |
#include <cstdio>
using namespace std;
int a,n,d,p,nr,aux;
int main()
{
freopen("inversmodular.in","r",stdin);
freopen("inversmodular.out","w",stdout);
scanf("%d %d\n",&a,&n);
nr=n;
p=n;
for(d=2;d*d<=n;d++)
if(!(n%d))
{
while(n%d==0)
n/=d;
p=(p/d)*(d-1);
if(n==1)
break;
}
if(n!=1)
p=n-1;
p--;
d=1;
while(p)
{
if(p%2==1)
d=(d*a)%nr;
a=(a*a)%nr;
p/=2;
}
printf("%d\n",d);
return 0;
}