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

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

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

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



 #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-２の答え\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の３答え %d個",ans);
 }