Cod sursa(job #1124135)
Utilizator | Bucevschi Alexandru alex_bucevschi | Data | 26 februarie 2014 11:30:20 |
---|---|---|---|
Problema | Invers modular | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.55 kb |
#include <cstdio>
using namespace std;
int n,m,a,i,mod;
int main()
{
freopen("inversmodular.in","r",stdin);
freopen("inversmodular.out","w",stdout);
scanf("%d%d",&a,&n);
m=1;mod=n;
for(i=2;i*i<=n;i++)
if(n%i==0)
{
m*=i-1;n/=i;
while(n%i==0)
{
m*=i;n/=i;
}
}
if(n>1)m*=n-1;
m--;i=1;
for(;m;m>>=1)
{
if(m&1)i=1LL*i*a%mod; //m&1==m%2
a=1LL*a*a%mod;
}
printf("%d\n",i);
return 0;
}