/* rep05.c
gcc rep05.c -o rep05 -lm
*/

#include<stdio.h>
#include<stdlib.h>
#include<time.h>

int mod(int a, int m)
{
	int b=a%m;
	return b<0 ?  b+m: b;
}

int gcd(int a, int b)
{
  return b==0 ? abs(a): gcd(b,a%b);
}

int euclid(int a, int b, int *x, int *y)
{
	int q,r,d0,x0,y0;
	if(b==0){
		if(a>=0){
			*x=1;
			*y=0;
			return(a);
		}
		else{
			*x=-1;
			*y=0;
			return(-a);
		}
	}
	else{
		q=a/b;
		r=a-q*b;
		d0=euclid(b,r,&x0,&y0);
		*x=y0;
		*y=x0-q*y0;
		return(d0);
	}
}

int chinese(int a, int b, int m, int n)
{
	int d,u,v,x;
	d=euclid(m,n,&u,&v);
	if(d!=1){
		printf("法が互いに素ではありません。\n");
		exit(1);
	}
	else
		return mod(a*n*v+b*m*u,m*n);
}

main()
{
	int a,b,m=0,n=0,x;
	
	srand(time(NULL));	// 乱数の初期化
	while(gcd(m,n)!=1){
		m=rand() % 500;
		n=rand() % 500;
	}
	a=rand() % m;
	b=rand() % n;
	x=chinese(a,b,m,n);
	printf("\n");	
	printf("連立合同式\n");	
	printf("  x = %5d ( mod %5d )\n",a,m);	
	printf("  x = %5d ( mod %5d )\n",b,n);
	printf("の解は\n");	
	printf("  x = %5d ( mod %5d )\n\n",x,m*n);
	printf("検算：\n");	
	printf("  %5d mod %3d = %3d\n",x,m,mod(x,m));	
	printf("  %5d mod %3d = %3d\n",x,n,mod(x,n));	
}