扩展欧几里得

#include<stdio.h>
int exgcd(int a, int b, int &x, int &y) 
{
	int d,tmp; 
	if (b==0) 
	{
		x = 1;
		y = 0; 
		return a;  
	} 
	d = exgcd(b,a%b,x,y); 
	tmp = x;
	x = y; 
	y = tmp - a/b * y;
	return d; 
} 
int main()
{
	int a,b,x,y,k;
	scanf("%d %d",&a,&b);
	k=exgcd(a,b,x,y);
	printf("%d %d %d\n",k,x,y);
	return 0;
}

中国剩余定理

#include <cstdio>  
#include <cstring>  
#include <iostream>  
using namespace std;  
int gcd(int a,int b,int &x,int &y)  
{
	
    int d,temp;
	if(b==0)   // 不定方程 a*x+b*y=gcd(a,b)=d;(x,y)为其一组整数解
	{
		x=1;
		y=0;
		return a;
	}  
    d = gcd(b,a%b,x,y); 
	temp = x;
	x = y; 
	y = temp - a/b * y;
	return d; 
}  

int main()  
{  
    int m,m1,r1,m2,r2,flag=0;
	int a[11],b[11],T;  
    cin>>T;  
    while(T--)  
    {     
        int i,j;
		int x,y,d,c,t;
		
		cin>>m;  
        for(i=0;i<m;i++)  
            cin>>a[i];  
        for(i=0;i<m;i++)  
            cin>>b[i]; 
		
		// x%m1=r1,x%m2=r2 ...
		// x=m1*k1+r1,x=m2*k2+r2 ... (k1,k2 ... 为任意整数)
		// m1*k1-m2*k2=r2-r1 ...
		
        flag=0;  
        m1=a[0];r1=b[0];  
        for(i=1;i<m;i++)  
        {  
            m2=a[i];r2=b[i];  
            if(flag)
				continue;  
            d=gcd(m1,m2,x,y);   // 方程 x*m1+y*m2=d=gcd(m1,m2);  
            c=r2-r1;  
            if(c%d)          //对于方程m1*x+m2*y=c=r2-r1，如果c不是d的倍数就无整数解  
            {  
                flag=1;  
                continue;  
            }
			//对于方程m1*x+m2*y=c=r2-r1,若(x0,y0)是一组整数解,那么(x0+k*(m2/d),y0-k*(m1/d))也是一组整数解(k为任意整数)  
			//其中x0=x*(c/d),y0=y*(c/d); (x,y为方程m1*x+m2*y=d=gcd(a,b)的一组整数解)
            t=m2/d;  
            x=(c/d*x+t)%t;    //保证x0是正数，因为x+k*t是解，(x%t+t)%t也必定是正数解(必定存在某个k使得(x%t+t)%t=x+k*t)  
            
			r1=m1*x+r1;  
            m1=m1*m2/d;  
        }  
        if(flag)
			cout<<0<<endl;  
        else              
            cout<<r1<<endl;    
    }  
    return 0;  
}