HDU-1576 (A/B) mod 9973 （扩展欧几里得算法）ACM小白 未完待续

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了HDU-1576 (A/B) mod 9973 （扩展欧几里得算法）ACM小白 未完待续，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1556字，纯文字阅读大概需要3分钟。

内容图文

http://acm.hdu.edu.cn/showproblem.php?pid=1576

先简介下扩展欧几里得算法：
据说可以证明方程ax+by=gcd(a，b)必然有解，而且不止一组解（gcd指最大公约数）
朴素的欧几里得算法就是辗转相除法，用来求gcd的
因为gcd(a，b)=gcd(b，a mod b)=gcd(a mod b，b mod (a mod b))=…
最后会有一方等于0，就能求出gcd(a，b)，这就是辗转相除法

扩展欧几里得算法可以解出方程ax+by=gcd(a，b)的一组解，假设a>b>=0
以下是一段简单的推导：
ax₁+by₁=bx₂+(a%b)y₂
             =bx₂+(a-[a/b]*b)y₂
             =ay₂+bx₂-[a/b]*by₂
             =ay₂+b(x₂-[a/b]*y₂)
至此可知x₁=y₂，y₁=x₂-[a/b]*y₂
（注：%表示mod，a-[a/b]*b等同于a mod b，[]表示向下取整）

因此，只要知道x₂，y₂就能知道x₁，y₁，而x₂，y₂也能通过x₃，y₃得知，这样往下递推到b=0为止

回到题目中，设X=A/B，
则
n=A%9973
  =A+[A/9973]*9973
  =XB+[A/9973]*9973

设x*B+9973*y=gcd(B，9973)=1，
则x*n*B+y*n*9973=n=XB+A/9973*9973
对比式子两边可知x*n=X
用扩展欧几里得算法算出方程x*B+9973*y=1的一组解
那么知道了x就知道X了，X就是A/B
X%9973（即x*n%9973）就是题目要的答案

但问题又来了，扩展欧几里得算法算出的x是负数怎么办？
负数取模再加一份模得到正数，然后输出即可，即x*n%9973+9973
（由于本人暂时也不太明白为何负数取模要想得到正数结果在这题当中可以这样转化，加上时间紧迫，只能回头再做补充了，至少代码能A）

#include<iostream>
using namespace std;
int exGcd(int a, int b, long long &x, long long &y)
{
	if (b == 0)
	{
		x = 1;
		y = 0;
		return a;
	}
	int r = exGcd(b, a%b, x, y);
	int t = x;
	x = y;
	y = t - a / b * y;
	return r;
}
int main()
{
	int T;
	cin >> T;
	long long n, B;
	long long x, y;
	for (T; T > 0; T--)
	{
		cin >> n >> B;
		exGcd(B, 9973, x, y);
		cout << x*n % 9973 + 9973 << endl;
	}
	return 0;
}

内容总结

以上是互联网集市为您收集整理的HDU-1576 (A/B) mod 9973 （扩展欧几里得算法）ACM小白 未完待续全部内容，希望文章能够帮你解决HDU-1576 (A/B) mod 9973 （扩展欧几里得算法）ACM小白 未完待续所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---