21 lines
322 B
C++
21 lines
322 B
C++
#include <iostream>
|
|
|
|
int mul_inv(int a, int b)
|
|
{
|
|
int b0 = b, t, q;
|
|
int x0 = 0, x1 = 1;
|
|
if (b == 1) return 1;
|
|
while (a > 1) {
|
|
q = a / b;
|
|
t = b, b = a % b, a = t;
|
|
t = x0, x0 = x1 - q * x0, x1 = t;
|
|
}
|
|
if (x1 < 0) x1 += b0;
|
|
return x1;
|
|
}
|
|
|
|
int main(void) {
|
|
std::cout << mul_inv(42, 2017) << std::endl;
|
|
return 0;
|
|
}
|