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

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

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