Cod sursa(job #1699460)
Utilizator | Data | 7 mai 2016 13:12:46 | |
---|---|---|---|
Problema | Invers modular | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.58 kb |
#include<cstdio>
int main()
{
long long n,a,s,d,p,cn,ca;
freopen("inversmodular.in","r",stdin);
freopen("inversmodular.out","w",stdout);
scanf("%lld%lld",&a,&n);
ca = a;
s=n;
cn=n;
d=2;
while(d*d <= n)
{
p=0;
while(n%d==0)
{
n/=d;
p++;
}
if(p != 0)
s=s/d*(d-1);
d++;
}
if(n != 1)
s = s/n*(n-1);
n=s-1;
p=1;
while(n!=0)
{
if(n%2!=0)
p=p*a%cn;
a=a*a%cn;
n/=2;
}
printf("%lld\n",p);
return 0;
}