算法竞赛进阶指南，153页，扩展欧几里得， 线性同余方程
本题要点： 1、同余方程 a * x = 1(mod m), 转化为 方程 a * x + b * y = 1, 利用 扩展欧几里得算法， 求出一组特解，x0 和 y0， x0 就是原来同余方程的一个解， 但是要求最小的正整数解， 只需要把 x0 同余模 到 1 ~ b 的范围内。 2、避免麻烦，直接 long long
#include <cstdio> #include <cstring> #include <iostream> using namespace std; typedef long long ll; ll exgcd(ll a, ll b, ll& x, ll& y) { if(!b) { x = 1, y = 0; return a; } ll d = exgcd(b, a % b, x, y); ll z = x; x = y; y = z - y * (a / b); return d; } int main() { ll a, b, x, y, ans = 0; scanf("%lld%lld", &a, &b); exgcd(a, b, x, y); while(x < 0) { x += b; } ans = x % b; printf("%lld\n", ans); return 0; } /* 3 10 */ /* 7 */