Cod sursa(job #1906834)
Utilizator | Data | 6 martie 2017 16:36:45 | |
---|---|---|---|
Problema | Invers modular | Scor | 70 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.55 kb |
#include <fstream>
#include <math.h>
#define MOD copie
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
unsigned long long a,b,nr=1,copie;
unsigned long i;
int main()
{
f>>a>>b;
int ok=1;
copie=b;
for(int k=2;k<=sqrt(b)&&ok;k++)
if(b%k==0) ok=0;
b--;
if(ok) b--;
while(b)
{
if(b&1)
{
nr=((nr%MOD)*(a%MOD))%MOD;
b--;
}
a=((a%MOD)*(a%MOD))%MOD;
b>>=1;
}
g<<nr%copie;
return 0;
}