Cod sursa(job #1696857)
| Utilizator | Data | 30 aprilie 2016 01:03:32 | |
|---|---|---|---|
| Problema | Invers modular | Scor | 0 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.67 kb |
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
long long k,i,m,x,j,ct,phi;
int main()
{
freopen("inversmodular.in","r",stdin);
freopen("inversmodular.out","w",stdout);
scanf("%lld%lld",&x,&m);
for(k=2;k<=sqrt(m);k++)
{
if(m%k==0)
ct+=2;
if(k==sqrt(m)&&m%k==0)
ct--;
}
if(ct==0)
phi=m-1;
else
phi=m-ct;
for(k=phi-1,j=1,i=x;k!=1;)
{
if(k%2==0)
{
k/=2;
i*=i;
}
else
{
k--;
j*=i;
}
}
printf("%lld\n",j*i%m);
return 0;
}
