【每日一题】洛谷 P1082（扩展欧几里得定理）
想她一次就背十个单词，当我英语过六级后，我就去告诉她，我很在意她
一天一道数论题，当我可以秒杀数论题的时候，就开始做 DP
今日份快乐：同余方程 传送门
明日份快乐：洛谷 P1297 传送门
求关于x 的同余方程 a * x ≡ 1(mod b) 的最小正整数解。
分析这个题就是个裸的数论题（废话）
a * x ≡ 1(mod b) ，即 a * x % b = 1 % b，也就是 a * x % b = 1.
根据取模运算，我们进行一波转化得到： a * x + b * y = 1，这里 y 是我们引入的一个变量，似乎是个负数。
很明显，这是一个二元一次方程，那肯定是要说扩展欧几里得定理啦~~
欧几里得定理：就是辗转相除法求最大公约数，用gcd（a，b）表示 a 和 b 的最大公因数
实现代码：
void gcd(int a, int b){
return b == 0 ? a : gcd(b, b % a);
}
扩展欧几里得定理：用来求 a * x + b * y = gcd(a, b) 的一组特解 (x0,y0)，并且是整数解
(数论太弱了，感觉自己解释不清楚这个，附上一份大佬的证明，传送门)
实现代码：
void extend_gcd(int a, int b, int &x, int &y){
if(b == 0){
x = 1, y = 0;
return;
}
extend_gcd(b, a % b, x, y);
int temp = x;
x = y;
y = temp - (a / b) * y;
}
二元一次方程 a * x + b * y = n 有整数的充要条件是 n % gcd(a, b) = 0；
我们回到题目中去，对于a * x + b * y = 1 ，题目保证一定有解，也就是说gcd(a, b) = 1，也就是 a 和 b 互质。
用扩展欧几里得定理得到方程的特解，但这个特解 (x0,y0) 不一定是我们要的最后的 x 为最小正整数解，这里我们要再进行一次转化，如下
a * x + b * y = 1
a * x + b * y + k * a * b - k * a * b = 1
a * (x + k * b) + b * (y - k * a) = 1
由最后的 a(x + kb) + b(y - ka) = 1，我看可以看出来 x 的通解为 x = x0 + k * b ， so，最小正整数解 x = (x0 % b)。因为x0可能是负数，直接取模得到的是负数，我们在取模的时候要留意一下，最终的答案就是 x = ( (x0 % b) + b) % b)。
附上AC代码:
#include
using namespace std;
void extend_gcd(int a, int b, int &x, int &y){
if(b == 0){
x = 1, y = 0;
return;
}
extend_gcd(b, a % b, x, y);
int temp = x;
x = y;
y = temp - (a / b) * y;
}
int main(){
ios::sync_with_stdio(false);
int a, b, x, y;
cin >> a >> b;
extend_gcd(a, b, x, y);
cout << (x % b + b) % b << endl;
return 0;
}
坚持的时候很狼狈，等成功以后，丑的还是丑的
