HDU 1576 A/B 扩展欧几里德算法 模线性方程入门题

发布时间:2016-12-9 6:17:50 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"HDU 1576 A/B 扩展欧几里德算法 模线性方程入门题",主要涉及到HDU 1576 A/B 扩展欧几里德算法 模线性方程入门题方面的内容,对于HDU 1576 A/B 扩展欧几里德算法 模线性方程入门题感兴趣的同学可以参考一下。

很详细的资料:http://blog.csdn.net/lulipeng_cpp/article/details/7612490 补充以下结论,自己推的,解释了以上博客里的疑惑。  方程ax+by=gcd(a,b),即 模线性方程ax≡d(mod b) ,令d = gcd(a,b)。假设 模线性方程的解为 x0, y0。 结论1:则有 max( abs(x0),abs(y0) ) < max( abs(a), abs(b) );  结论2:若d = a, 则 x = 1,y = 0; 若 d = b,则 x = 0,y = 1; 结论3:则方程的所有解为 x = x0 + b/d*i, y = y0 - a/d*i。(i = 0, +1, -1, +2, -2, ..........);           且 abs(x0) < b/d, abs(y0) < a/d;  该模线性方程的最小正整数解(x) 为  min(x) = ( x + b ) % b; 结论4:如果要求方程ax+by=w(   即ax≡w(mod b)   )的解, 模线性方程有解的充要条件为d|w,令 t = w/d;           方程的所有解为x = (x0 + b/d*i) * t, y = (y0 - a/d*i) * t。(i = 0, +1, -1, +2, -2, ..........);           该模线性方程的最小正整数解(x) 为  min(x) = (x*t + b )% b; 注意: 结论4最后一行 x*t可能超int(HDU这题没超),以后做题需要注意这点,最好模板都写成__int64 View Code #include<cstdio> #include<cstring> #define LL __int64 LL ex_gcd(LL a, LL b, LL &x, LL &y) //模板 { if(!b) { x = 1; y = 0; return a;} else { LL t = ex_gcd(b, a%b, x, y); LL tmp = x; x = y; y = tmp - a/b * y; return t; } } int main() { LL x, y, n, b; int cas; scanf("%d", &cas); while(cas--) { scanf("%I64d%I64d", &n, &b); ex_gcd(b, 9973, x, y); x = ( (x * n % 9973 ) + 9973 ) % 9973; // x*n注意可能会超int printf("%d\n", x); } return 0; }  

上一篇:JAVA的Date类与Calendar类
下一篇:CGI原理及其性能

相关文章

相关评论