[luoguP1516] 青蛙的约会（扩展欧几里得）传送门

对于数论只会gcd的我，也要下定决心补数论了

列出方程

(x + t * m) % l = (y + t * n) % l

那么假设 这两个式子之间相差 num 个 l，即为

x + t * m = y + t * n +

[HDU1576] A/B（扩展欧几里得）传送门

n = A % 9973 > n = A A / 9973 * 9973
设 x = A / B（题目所述，B|A） > A = B * x
所以 B * x A / 9973 * 9973 = n
设 y = A / 9973
则 B * x 9973 * y = n
B 和 n

[luoguP1082] 同余方程（扩展欧几里得）传送门

ax≡1(mod b)
这个式子就是 a * x % b == 1 % b
相当于 a * x b * y == 1
只有当 gcd(a,b) == 1 时才有解，也就是说 ax + by = c 有解的充要条件是 c % gcd(a,b) =

基本数论算法dalao博客，至少很好看。。

因为本人数论实在渣渣，但是考试确是得考的，只好尽早学，尽早掌握。

最大公因数

普通gcd
O(log(min(a,b)))


1 inline int gcd(int x,int y)
2