C++ 数论相关题目 扩展欧几里得算法（裴蜀定理）
给定 n
对正整数 ai,bi
，对于每对数，求出一组 xi,yi
，使其满足 ai×xi+bi×yi=gcd(ai,bi)
。
输入格式
第一行包含整数 n
。
接下来 n
行，每行包含两个整数 ai,bi
。
输出格式
输出共 n
行，对于每组 ai,bi
，求出一组满足条件的 xi,yi
，每组结果占一行。
本题答案不唯一，输出任意满足条件的 xi,yi
均可。
数据范围
1≤n≤105
,
1≤ai,bi≤2×109
输入样例：
2
4 6
8 18
输出样例：
-1 1
-2 1
没什么好说的，理解公式背模板！
#include <iostream>using namespace std;int n;int exgcd(int a, int b, int &x, int &y)
{if(!b) //边界情况，b=0{x = 1, y = 0; //求系数return a;}int d = exgcd(b, a % b, y, x); // 递归求最大公约数,求的是by+ax，换下xy的位置。y -= a / b * x;return d;
}int main ()
{cin >> n;while(n -- ){int a, b, x, y;cin >> a >> b;exgcd(a, b, x, y);cout << x << ' ' << y << endl;}return 0;}
输入输出比较多的情况下，可以用scanf和printf节省时间。