「ax+by型の整数と一次の不定方程式」の編集履歴(バックアップ)一覧に戻る

ax+by型の整数と一次の不定方程式 - (2012/12/06 (木) 18:09:19) のソース

大学への数学 マスターオブ整数論
*問い10-2
方程式7x-5y=1の媒介変数表示を求めよ。
ax+by=1の媒介変数表示への変換、a,bは互いに素とする。
整数論は中学レベルの教育すら受けてないのですごくあやしい関数を書いてます。


 #include<stdio.h>
 int gcd(int a, int b){
    while( 1 ){
        a = a % b;
	if( a == 0 )return b;
	b = b % a;
        if( b == 0 )return a;
    }
 }
 void saiki(int a1,int a2,int& a3,int& a4,int deep){
	if(a2!=0&&a1!=0){
		int k=gcd(a1,a2);
		a1/=k;
		a2/=k;
	}
	//printf("(%d %d %d)",deep,a1,a2);
	if(a2==-1||a2==1){
		a3=0;
		a4=-a2;
		return ;
	}
	if(a1==-1||a1==1){
		a3=a1;
		a4=0;
		return ;
	}
	if(a1==0){
		a3=0;
		a4=a2>0?1:-1;
		return;
	}
	if(a2==0){
		a3=a1>0?1:-1;
		a4=0;
		return ;
	}
	if(a1%a2==1){
		if(deep%2==0){
			a3=1;
			a4=a1/a2;
		}else{
			a3=-a1/a2;
			a4=-1;
		}
		//printf("\n");
		return ;
	}
	int re1,re2;
	saiki(a2,a1-a2*(a1/a2),re1,re2,deep+1);
	if(deep%2==0){
		a3=re1;
		a4=re1*(a1/a2)+re2;
	}else{
		a3=re2*(a1/a2)+re1;
		a4=re2;
	}
	//printf("(%d %d %d)",deep,a3,a4);
	//if(deep==0)printf("(%d %d %d %d)",a1,a3,a2,a4);
 
	return ;
 }
 int main(){
	int ansX,ansY,a,b;
	while(1){
		scanf("%d %d",&a,&b);
		b=-b;
		saiki(a,b,ansX,ansY,0);
		if(a*ansX-b*ansY==-1){
			ansY=-ansY;
			ansX=-ansX;
		}
		
		//printf("答は%d*%d-%d*%d=%d\n",a,ansX,b,ansY,a*ansX-b*ansY);
		printf("\nx=%d*m+%d,y=%dm+%d\n",b,ansX,a,ansY);
	}
 }