Cod sursa(job #1885955)
Utilizator | Data | 20 februarie 2017 16:07:15 | |
---|---|---|---|
Problema | Suma si numarul divizorilor | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.52 kb |
#include <cstdio>
using namespace std;
void gcd(int x, int y, int &a, int &b) {
if(y == 0) {
a = 1;
b = 0;
} else {
gcd(y, x % y, a, b);
int backup = a;
a = b;
b = backup - b * (x / y);
}
}
int main() {
freopen("inversmodular.in", "r", stdin);
freopen("inversmodular.out", "w", stdout);
int a, n, x, y;
scanf("%d%d", &a, &n);
gcd(a, n, x, y);
if(x <= 0)
x = n + x % n;
printf("%d\n", x);
return 0;
}