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

「ax+by型の整数と一次の不定方程式」の編集履歴(バックアップ)一覧に戻る
ax+by型の整数と一次の不定方程式」を以下のとおり復元します。
大学への数学 マスターオブ整数論
*問い10-2と問い10-3
方程式7x-5y=1の媒介変数表示を求めよ。
ax+by=1の媒介変数表示への変換、a,bは互いに素とする。
整数論は中学レベルの教育すら受けてないのですごくあやしい関数を書いてます。

問い10-3
11x-8y=1、0<x<=100,0<y<=100を満たすxとyの組の数。



 #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;
	printf("ax+by=1の媒介変数表示を求めます。(a,bは互いに素)a,bを入力して下さい。\n");
	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("問い10-2の答え\nx=%d*m+%d,y=%dm+%d\n",b,ansX,a,ansY);
	printf("問い10-3ax+by=1かつ0<x<=100 0<y<=100を満たすxyの組を求めます。\n");
	scanf("%d %d",&a,&b);
	saiki(a,b,ansX,ansY,0);
	if(a*ansX-b*ansY==-1){
		ansY=-ansY;
		ansX=-ansX;
	}
	if(b<0)b=-b;
	if(a<0)a=-a;
	while(ansY<0)ansY+=b;
	while(ansX<0)ansX+=a;
	int ans1=0,ans2=0,ans=0;
	if(ansY<=100)ans2=(100-ansY)/b+1;
	if(ansX<=100)ans1=(100-ansX)/a+1;
	ans=ans1>ans2?ans2:ans1;
	printf("問い10の3答え %d個",ans);
 }

復元してよろしいですか?