※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

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

ax+by型の整数と一次の不定方程式 - (2012/12/06 (木) 18:08:09) の編集履歴(バックアップ)


大学への数学 マスターオブ整数論

問い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);
}
}