HDU 1576 扩展欧几里德算法求二元一次不定方程

看完数论数的这一段，觉得这个算法太精辟了，其实扩展欧几里德算法就是书上的公式翻译成代码，实在是太棒了，我还SB似的去纠结过程，其实自己已经会笔算了

可是书上的第二种解二元一次不定方程方法，目前还在纠结中...

运用的定理中的推论得出一定存在整数 x , y 使得  ax + by =gcd( a,b); 成立.    同样有定理得到  如果  ax  + by = n  有解，则 gcd( a,b )  | n  一定成立

令  a1 = a | gcd( a,b );  b1 = b | gcd( a,b ) ;  n1 = n | gcd( a,b ) ;  ( a1 , b1 ) =1 ;  所以 ax +by = n; 和 a1x + b1y = n1 ; 的解是一样的， 所以要求 a1 x + b1y = n1 的通解

则必须求一特解，则就解方程 a1x + b1y=1; 解的解（x' , y' )  ,扩展解（ x'+t*b1 , y'-t*a1 ）t = 1,2,3,4,....    利用数论书上第一章的定理来解方程..

 则翻译成代码就成了 所谓的扩展欧几里得算法...

解提报告：

题意中说，A 必能被B整除，那么令 A = BX ;  因为 n = A % 9973， 所以 n=A-A/9973*9973。又 A/B = x ，则 A=Bx。所以 Bx-A/9973*9973=n。即 Bx-9973y=n。

到这里我们可以发现：只要求出 x 的值，即可算出 x%9973，也就是 (A/B)%9973 了。顺利解决了！

#include<iostream>
using namespace std;
int x,y;
void kzgcd(int a,int b){  模板
    if(!b) x=1,y=0;
    else{
        kzgcd(b,a%b);
        int t=y;
        y = x-(a/b)*y;
        x=t;
    }    
}
int main(){
    int t,n,b;
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&b);
        kzgcd(b,9973);
        while(x<0){     防止出现负数情况
            x += 9973;
        }
        printf("%d\n",x*n%9973);
    }
}