Cod sursa(job #1895802)
Utilizator | Data | 28 februarie 2017 11:07:49 | |
---|---|---|---|
Problema | Invers modular | Scor | 10 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.45 kb |
#include <fstream>
#include <math.h>
using namespace std;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
unsigned long long a,b,nr;
unsigned long i;
int main()
{
f>>a>>b;
int ok=1;
for(int k=2;k<=sqrt(b)&&ok;k++)
if(b%k==0) ok=0;
b--;
if(ok) b--;
for(nr=1,i=(1<<31);i;i>>=1)
{
nr*=nr;
if(i&b) nr*=a;
}
if(ok) g<<nr%(b+2);
else g<<nr%(b+1);
return 0;
}