Cod sursa(job #2397648)
Utilizator | Alghisi Alessandro Paolo alexalghisi | Data | 4 aprilie 2019 17:36:48 |
---|---|---|---|
Problema | Invers modular | Scor | 100 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.46 kb |
#include <iostream>
#include <fstream>
#define LL long long
using namespace std;
void gcd(LL &x,LL &y,int a,int b){
if(b==0){
x=1;
y=0;
return;
}
gcd(x,y,b,a%b);
LL aux = x;
x = y;
y = aux - y*(a/b);
}
int main()
{
int a,n;
LL inv = 0,ins;
ifstream f("inversmodular.in");
ofstream g("inversmodular.out");
f>>a>>n;
gcd(inv,ins,a,n);
if(inv<=0)
inv = n + inv%n;
g<<inv;
return 0;
}