题目分类列表 当前分类: 扩展欧几里得算法 (#include <iostream>
using namespace std;

//扩展欧几里德算法
int ExGCD(int a, int b, int& x, int& y)
{
if(b == 0)
{
x = 1, y = 0;
return a;
}
int d = ExGCD(b, a%b, x, y);
int temp = x;
x = y;
y = temp - a/b*y;
return d;
}

int main()
{
int x, y, d;
d = ExGCD(99, 78, x, y);
cout << d << " " << x << " " << y << endl;
return 0;
}

//定理一: 如果a,b是不都为0的任意整数,则d=gcd(a,b)是a,b的线性组合{ax+by: x,y∈Z}的最小元素.
// 已知d=gcd(a,b)=gcd(b,a mod b)
//
//由gcd(b,a mod b)得知,d = bx + a mod b = bx + (a-floor(a/b)*b)*y = a*y + b(x-floor(a/b)*y)
//当推到gcd(a,b)时,d′ = d = a*y + b(x-floor(a/b)*y)

//其他比较重要定理:
//定理二:d|a, d|b => d|(ax+by)  注:d|a表示a mod b == 0,即a能被b整除
//定理一推论: 对任意整数a,b如果d|a,d|b,则d|gcd(a,b)

//附:
int GCD(int a, int b)
{
    if(b == 0)
  return a;
  return GCD(b, a % b);
}
//迭代形式:
int GCD(int a, int b)
{
while(b != 0)
{
int r = b;
b = a % b;
a = r;
}
return a;
})
PID 题目名称 文件名称 时间 空间 难度 评测方式 通过 提交 通过率
333 [NOI 2002] 荒岛野人 savage 2 s 128 MB ★★ 简单对比 125 411 30.41%
1225 倒酒 pour 1 s 128 MB ★★ 简单对比 85 293 29.01%
1265 [NOIP 2012] 同余方程 mod 1 s 128 MB ★☆ 简单对比 427 1131 37.75%
1677 [POJ 1061] 青蛙的约会 poj_hama 1 s 256 MB ★★ 简单对比 109 355 30.7%
1786 韩信点兵 HanXin 1 s 256 MB ★★☆ 简单对比 170 648 26.23%
1965 [HAOI 2015] 按位或 haoi2015_set 1 s 256 MB ★★★☆ 评测插件 19 54 35.19%
2057 [ZLXOI2015]殉国 BlackHawk 0.05 s 256 MB ★☆ 评测插件 83 522 15.9%
2160 丧心病狂的韩信大点兵 weakhanxin 1 s 256 MB ★★★ 简单对比 43 183 23.5%
2547 军队 tarmy 1 s 256 MB ★☆ 简单对比 34 131 25.95%
2888 [Code+201712Div2]可做题2 solve2 1 s 256 MB ★★☆ 简单对比 8 21 38.1%
2946 [POJ 2115] C Looooops cloops 1 s 256 MB ★☆ 简单对比 8 27 29.63%