ユークリッドの互助法 - c21coterie @ ウィキ

問い7-1

昭和１年は西暦１９２６年である。
昭和で西暦を割り切れる年はいくつあるか？

#include<stdio.h>
void calc(int n,int m){
int ans=0;
for(int i=1;i<=n;i++){
	if((m+i)%i==0)ans++;
}
printf("%d",ans);
}
int main(){
calc(64,1925);
}

問い7-2

3007と1649の約数。

#include<stdio.h>
int gcd ( int a, int b ){
int c;
while ( a != 0 ) {
   		c = a; a = b%a;  b = c;
	}
 	return b;
}
int main(){
printf("%d",gcd(1649,3007));
}

問い7-３

7ｎ+1と8ｎ+4の最大公約数が5になるような１００以下の自然数ｎは全部でいくつあるか？
もう少し効率的に計算してもいいかも。

#include<stdio.h>
int gcd ( int a, int b ){
int c;
while ( a != 0 ) {
  		c = a; a = b%a;  b = c;
}
	return b;
}
void saiki(int a1,int b1,int a2,int b2,int mod,int limit){
if(a2==0){
	printf("\n(%dn+%d=%dn+%d)\n ans=",a1,b1,a2,b2);
	if(b2<0)b2=-b2;
	for(int i=mod;i<=limit;i+=mod){
		if(gcd(i,b2)==mod){
			printf("%d ",i-b1);
		}
	}
	return ;
}
	
int a3=a1/a2;
int b3=b1-a3*b2;
int a4=a1-a2*a3;
printf("\n(%dn+%d=%d(%dn+%d)+%dn+%d)",a1,b1,a3,a2,b2,a4,b3);
saiki(a2,b2,a4,b3,mod,limit);
}
int main(){
saiki(8,4,7,1,5,100);
}

問い7-4

26ｘ+111ｙ＝1の解を一つ求めよ。
本とにらめっこすること１時間。
整数論の教育は中学生レベルですら受けてないので数式の意味を理解して、それをプログラムに翻訳するのに時間かかった。
このへんで普通高校レベル？
プログラムの方が楽かも、もし数式を覚えてペンシルアンドペーパーで解けと言われたら困る気がする。
プログラムにバグがあったので修正。
これで大丈夫だと思う多分。
備考
a,bが自然数の時正しい答えを返す。
解がない時は１に一番近い答えが返ってくる。
整数論の勉強用なので大きな数を入れると桁あふれをおこす。
答えに-１が出た時はｘ、ｙの符号を反転してください。

問い7-5はこの関数の絶対値を取ればいいだけなので割愛。

#include<stdio.h>
#include<stdlib.h>
int gcd ( int a, int b ){
int c;
while ( a != 0 ) {
   		c = a; a = b%a;  b = c;
	}
 	return b;
}
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("(%1d %3d %3d)",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=1;
	return;
}
if(a2==0){
	a3=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("(%1d %3d %3d)",deep,a3,a4);
return ;
}
int main(){
int ansX,ansY;
int a,b;
printf("ax+by=1のaとbをスペースを区切って整数で入力してください。(a,b)\n");
scanf("%d %d",&a,&b);
saiki(a,b,ansX,ansY,0);
printf("\n答は\n%d*%d-%d*%d=%d",a,ansX,b,ansY,a*ansX-b*ansY);

}

問い7-6

f(n)=an^3+bn^2+cn+d
g(n)=en^3+fn^2+gn+h
a,b,c,d,e,f,g,hを全て整数の定数とする。
この時gcd(f(x),g(x))が最大となる整数ｘを求める問題。

互助法で割り切っていって一次関数が出てくれば解あり？
出てこなければｇｃｄは無限大まで大きくなる？
のか、変数が多すぎて全然わからないのでコードもまったく自信がありません。

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
int gcd ( int a, int b ){
int c;
while ( a != 0 ) {
	c = a; a = b%a;  b = c;
}
return b;
}

void print(int a[4]){
printf("(");
	for(int i=0;i<4;i++)printf("%d ",a[i]);
printf(")");
}
void saiki(int a1[4],int a2[4],int badCount){
if(a2[0]==0&&a2[1]==0&&a2[2]==0){
	printf("\n");
	print(a1);
	print(a2);
	if(a1[2]==0){
		printf("ans=無限大\n");
	}else if((a2[3]-a1[3])!=0){
		printf("ans=%d",a2[3]-a1[3]/a1[2]);
	}else{
		printf("ans=1");
	}
	return ;
}

int check[4];
int roopSize=0,top=0;
for(int i=0;i<4;i++)check[i]=a1[i];
for(int i=0;i<4;i++){
	if(a2[i]!=0)break;
	roopSize++;
}
for(int i=0;i<4;i++){
	if(a1[i]!=0)break;
	top++;
}
printf("(top=%d loop=%d)\n",top,roopSize);

for(int i=top;i<=roopSize;i++){
	int k,p;
	printf("%d ",i);
	k=a1[i]/a2[roopSize];
	for(int j=0;j<4-roopSize;j++){
		a1[j+i]-=k*a2[j+roopSize];
	}
	print(a1);
	printf("\n");
}
printf("左 ");
print(a2);
printf("右 ");
print(a1);
bool nextOK=false;
for(int i=0;i<4;i++){
	if(a1[i]!=check[i])nextOK=true;
}
if(nextOK==true){
	saiki(a2,a1,0);
	}else if(badCount==0){
	saiki(a2,a1,1);
}else{
	printf("ans=無限大");
}
}

int main(){
int a1[4],a2[4];
printf("an^3+bn^2+cn+dとen^3+fn^2+gn+hの最大公約数の最大値を求めます\n");
printf("a b c dを入力してください。\n");
scanf("%d %d %d %d",&a1[0],&a1[1],&a1[2],&a1[3]);
printf("e f g hを入力してください。\n");
scanf("%d %d %d %d",&a2[0],&a2[1],&a2[2],&a2[3]);
saiki(a1,a2,0);
}