模板：

 

int Extend_Euclid(int a, int b, int &x, int &y){

        if(b == 0){

            x = 1; 

            y = 0;

            return a;

        }

        else{

            int gcd,t;

            gcd = Extend_Euclid(b, a%b, x, y);

            t = x;

            x = y;

            y = t - (a / b) * y;

            return gcd;

        }

    }

详见：

hdu 2669

 

Sample Input

77 51 10 44 34 79

 

 

Sample Output

2 -3 sorry 7 -3

 

 

求 a*x + b*y = 1。输出一个正数x，一个y。

直接套模板，最后对x < 0时处理一下，∵a*x + b*y = 1，所以x+=b，y-=a来保持值不变

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            typedef long long ll;typedef unsigned long long ull;using namespace std;const int N=100050;ll ex_gcd(ll a,ll b,ll &x,ll &y) //扩展欧几里德{ if(b ==0) { x = 1;y = 0; return a; } else { ll t = ex_gcd(b,a%b,y,x); y = y - x*(a/b); return t; }}int main(){ ll a,b; while(scanf("%I64d%I64d",&a,&b)!= EOF) { ll x,y; ll tmp = ex_gcd(a,b,x,y); if(1 % tmp) printf("sorry\n"); else { while(x < 0){ x += b; y -= a; } printf("%I64d %I64d\n",x,y); } } return 0;}
           
          
         
        
       
      
     

　　

hdu 1576

 

Problem Description

要求(A/B)%9973，但由于A很大，我们只给出n(n=A%9973)(我们给定的A必能被B整除，且gcd(B,9973) = 1)。

 

 

Input

数据的第一行是一个T，表示有T组数据。

每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。

 

 

Output

对应每组数据输出(A/B)%9973。

 

 

Sample Input

2 1000 53 87 123456789

 

 

Sample Output

7922 6060

 

 

A % B = 0，A= Bx；

n = A%9973  , A  = 9973y + n;   Bx -9973y  = n;

GCD(b,9973) = 1,      b*x1 + 9973y1 = 1,    b*x1*n + 9973 *(n*y1) = n

∴ x = n*x1,  x1可以通多exGCD算出

最后的x通过    (x % MOD + MOD)%MOD 防止出现负数

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            typedef long long ll;typedef unsigned long long ull;using namespace std;const int N=100050;void ex_gcd(int a,int b,int &x,int &y) //扩展欧几里德{ if(b ==0) { x = 1;y = 0; } else { ex_gcd(b,a%b,y,x); y = y - x*(a/b); }}int main(){ int T; scanf("%d",&T); while(T--) { int n,B; scanf("%d%d",&n,&B); int x,y; ex_gcd(B,9973,x,y); x *= n; printf("%d\n",(x%9973 + 9973)% 9973); //再加上一次，防止负 } return 0;}