Pagini recente » Cod sursa (job #2214758) | Cod sursa (job #2093469) | Cod sursa (job #219837) | Cod sursa (job #1703837) | Cod sursa (job #397647)
Cod sursa(job #397647)
#include<cstdio>
long long nr,a,n;
long long phi(long long n)
{
long long p=n,d,e;
d=2;
while(n>1)
{
e=0;
while(n%d==0)
{
e++;
n=n/d;
}
if(e!=0)
{p=p/d; p=p*(d-1);}
d++;
}
return p;
}
long long putlog(long long a, long long p)
{
long long pp;
pp=1;
while(p)
{
if(p&1)
{
pp*=a;
pp=pp%n;
}
a=a*a;
pp=pp%n;
p>>=1;
}
return pp;
}
int main()
{
freopen("inversmodular.in","r",stdin);
freopen("inversmodular.out","w",stdout);
scanf("%lld%lld",&a,&n);
nr=phi(n);
printf("%lld",putlog(a,nr-1));
return 0;
}