很详细的资料：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 #include #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 ", x); } return 0; }