Romantic HDU - 2669(扩欧模板题)
2019-08-16 08:01:40来源:博客园 阅读 ()
Romantic HDU - 2669(扩欧模板题)
扩展欧几里得模板
扩展欧几里德算法——找出一对整数(x,y), 使得ax+by = gcd(a,b)。 注意, 这里的x和y不一定是正数, 也可能是负数或者0。 例如, gcd(6,15)=3,6*3-15*1=3
, 其中x=3, y=-1。 这个方程还有其他解, 如x=-2, y=1。
void gcd(int a, int b, int& d, int &x, int &y)
{
if(!b)
{
d = a;
x = 1;
y = 0;
}
else
{
gcd(b, a % b, d, y, x);
y -= x * (a / b);
}
}
用数学归纳法并不难证明该算法的正确性, 此处略去。 注意在递归调用时, x和y的顺序变
了, 而边界也是不难得出的:gcd(a,0)=1?a-0*0=a
。 这样, 唯一需要记忆的是y-=x*(a/b), 哪
怕暂时不懂得其中的原因也不要紧。
上面求出了ax+by=gcd(a,b)的一组解(x1,y1), 那么其他解呢? 任取另外一组解(x2,y2),
则ax1+by1=ax2+by2( 它们都等于gcd(a,b)) , 变形得a(x1-x2)=b(y2-y1)。 假设gcd(a,b)=g, 方程
左右两边同时除以g, 得a'(x1-x2)=b' (y2-y1), 其中a'=a/g, b'=b/g。 注意, 此时a'和b'互素,
因此x1-x2一定是b'的整数倍。 设它为kb', 计算得y2-y1=ka'。 注意, 上面的推导过程并没有用
到“ax+by的右边是什么”, 因此得出如下结论。
即:设a, b, c为任意整数。 若方程ax+by=c的一组整数解为(x0,y0), 则它的任
意整数解都可以写成(x0+kb', y0-ka'), 其中a'=a/gcd(a,b), b'=b/gcd(a,b), k取任意整数。
以上内容均参考自刘汝佳的《算法竞赛入门经典》
题目代码及讲解
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
void gcd(LL a, LL b, LL &d, LL &x, LL &y)
{
if(!b)
{
d = a;
x = 1;
y = 0;
}
else
{
gcd(b, a % b, d, y, x);
y -= x * (a / b);
}
}
int main()
{
std::ios::sync_with_stdio(false);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
LL a, b;
LL x, y;
while(cin >> a >> b)
{
LL x, y, d;
gcd(a, b, d, x, y); //在这里产生一组解
if(d != 1) //要满足题目所给的等式,就必须要求a, b的最大公约数为1
cout << "sorry" << endl;
else
{
while(x < 0)
{
x += b / 1; //它的任意整数解都可以写成(x0+kb', y0-ka'),直到x不为负数为止
y -= a / 1;
}
cout << x << " " << y << endl;
}
}
}
原文链接:https://www.cnblogs.com/KeepZ/p/11342116.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- HDU-2955-Robberies(0-1背包) 2020-03-30
- hdu1455 拼木棍(经典dfs) 2020-02-29
- anniversary party_hdu1520 2020-02-16
- hdu1062 text reverse 2020-01-27
- hdu4841 2020-01-26
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash