#include <iostream> using namespace std; // 扩展欧几里得算法，求解 ax + by = gcd(a, b) 的解 (x, y) // 返回 gcd(a, b)，并通过引用参数返回 x 和 y long long extended_gcd(long long a, long long b, long long &x, long long &y) { if (b == 0) { x = 1; y = 0; return a; } long long x1, y1; long long gcd = extended_gcd(b, a % b, x1, y1); x = y1; y = x1 - (a / b) * y1; return gcd; } // 求解 ax ≡ 1 (mod b) 的最小正整数解 long long mod_inverse(long long a, long long b) { long long x, y; extended_gcd(a, b, x, y); // 调整 x 为最小正整数解 return (x % b + b) % b; } int main() { long long a, b; cin >> a >> b; cout << mod_inverse(a, b) << endl; return 0; }