Cod sursa(job #927235)
| Utilizator | Data | 25 martie 2013 17:58:50 | |
|---|---|---|---|
| Problema | Invers modular | Scor | 0 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.5 kb |
#include <iostream>
#include<cstdio>
using namespace std;
long long a,n,e,i,m,x;
int main()
{
freopen("inversmodular.in","r",stdin);
freopen("inversmodular.out","w",stdout);
cin>>a>>n;
e=1;m=n;
for(i=2;i*i<=n;i++)
if(n%i==0)
{
while(n%i==0)
{
n/=i;
e*=i;
}
e/=i;e*=i-1;
}
if(n>1) e*=n-1;
e--;
x=1;
while(e)
{
if(e%2)
x=(x*a)%m;
a=(a*a)%m;
}
cout<<x;
return 0;
}
