「余りの処理」の編集履歴（バックアップ）一覧はこちら

「余りの処理」(2012/11/28 (水) 14:29:24) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

マスターオブ整数論大学への数学
*問い6-1
７で割ると５余り、９で割ると７余り１１で割ると３余る数のうち３番目に小さいもの。
効率の悪い解法。

問い6-1-２
7で割ると１余り９で割ると２あまり、１１で割ると３余る自然数のうち最も１０００に近いもの。

 #include<stdio.h>
 int calc(int a1,int b1,int a2,int b2,int a3,int b3){
	//この関数は小さい数だけ取り扱えます
	int stop=(a1*a2*a3)+a1+a2+a3+b1+b2+b3;
	while(1){
		if(stop<b1||stop<b2||stop<b3)break;
		if(b1==b2&&b2==b3){
			return b3;
		}
		if(b1<=b2&&b1<=b3){
			b1+=a1;
		}else if(b2<=b3&&b2<=b1){
			b2+=a2;
		}else if(b3<=b1&&b3<=b2){
			b3+=a3;
		}
	}
	printf("解なし");
	return -1;
 }
 int main(){
	printf("問い6-1-1の答え%d\n",calc(7,5,9,7,11,3)+7*9*11*2);
	int t=calc(7,1,9,2,11,3);
	int ans=t;
	while(t<1000){
		t+=7*9*11;
		ans=t;
	}
	ans=t-1000>1000-ans?ans:t;
	printf("問い6-1-2の答え%d",ans);
 }




*問い6-２
１１を足しても１３で割りきれ、１３を足しても１１で割り切れる数のうち二番目に小さいもの。
足す数が互いに素な数で動く関数、それ以外は条件を満たす適当な数を返す。

 #include<stdio.h> 
 int gcd ( int a, int b ){
	int c;
	while ( a != 0 ) {
     		c = a; a = b%a;  b = c;
  	}
  	return b;
 }
 void calc(int a,int b){
	int k=gcd(a,b);
	int c=a*(b/k);
	printf("%d",c*2-a-b);
 }
 int main(){
	calc(13,11);
 } 





*問い6-3
5631,5839,5995をｘで割ったところ、余りが同じになった。
ｘ＞＝28となる数を全て求めよ。

 #include<stdio.h>
 int gcd ( int a, int b ){
	int c;
	while ( a != 0 ) {
    		c = a; a = b%a;  b = c;
 	}
 	return b;
 }
 int calc(int m,int n,int r){
	int a=n-m;
	int b=r-m;
	printf("%d",gcd(a,b));
 }
 int main(){
	calc(5631,5839,5995);
 }





*問い6-4
ｎ以下の数ｍをｍ^2をｎで割った時余りが１になる数の個数。
基本手抜き。
桁あふれ対策も考えるとこれちょっとした難問になるなあ。
桁あふれ対策どうする？

 #include<stdio.h>
 int calc(int n){
	int ans=0;
	for(int i=1;i<n;i++){
		ans+=((i*i)%n==1);
	}
	printf("%d\n",ans);
 }
 int main(){
	calc(120);
 }

マスターオブ整数論大学への数学
*問い6-1
７で割ると５余り、９で割ると７余り１１で割ると３余る数のうち３番目に小さいもの。
効率の悪い解法。

問い6-1-２
7で割ると１余り９で割ると２あまり、１１で割ると３余る自然数のうち最も１０００に近いもの。

 #include<stdio.h>
 int calc(int a1,int b1,int a2,int b2,int a3,int b3){
	//この関数は小さい数だけ取り扱えます
	int stop=(a1*a2*a3)+a1+a2+a3+b1+b2+b3;
	while(1){
		if(stop<b1||stop<b2||stop<b3)break;
		if(b1==b2&&b2==b3){
			return b3;
		}
		if(b1<=b2&&b1<=b3){
			b1+=a1;
		}else if(b2<=b3&&b2<=b1){
			b2+=a2;
		}else if(b3<=b1&&b3<=b2){
			b3+=a3;
		}
	}
	printf("解なし");
	return -1;
 }
 int main(){
	printf("問い6-1-1の答え%d\n",calc(7,5,9,7,11,3)+7*9*11*2);
	int t=calc(7,1,9,2,11,3);
	int ans=t;
	while(t<1000){
		t+=7*9*11;
		ans=t;
	}
	ans=t-1000>1000-ans?ans:t;
	printf("問い6-1-2の答え%d",ans);
 }




*問い6-２
１１を足しても１３で割りきれ、１３を足しても１１で割り切れる数のうち二番目に小さいもの。
足す数が互いに素な数で動く関数、それ以外は条件を満たす適当な数を返す。

 #include<stdio.h> 
 int gcd ( int a, int b ){
	int c;
	while ( a != 0 ) {
     		c = a; a = b%a;  b = c;
  	}
  	return b;
 }
 void calc(int a,int b){
	int k=gcd(a,b);
	int c=a*(b/k);
	printf("%d",c*2-a-b);
 }
 int main(){
	calc(13,11);
 } 





*問い6-3
5631,5839,5995をｘで割ったところ、余りが同じになった。
ｘ＞＝28となる数を全て求めよ。

 #include<stdio.h>
 int gcd ( int a, int b ){
	int c;
	while ( a != 0 ) {
    		c = a; a = b%a;  b = c;
 	}
 	return b;
 }
 int calc(int m,int n,int r){
	int a=n-m;
	int b=r-m;
	printf("%d",gcd(a,b));
 }
 int main(){
	calc(5631,5839,5995);
 }





*問い6-4
ｎ以下の数ｍをｍ^2をｎで割った時余りが１になる数の個数。
基本手抜き。
桁あふれ対策も考えるとこれちょっとした難問になるなあ。
桁あふれ対策どうする？
問い6-5
３で割ると1余り、５で割ると４余り、７で割ると３余る自然数のうち最小のもの。

 #include<stdio.h>
 void calc(int n){
	int ans=0;
	for(int i=1;i<n;i++){
		ans+=((i*i)%n==1);
	}
	printf("問い6-4答え%d\n",ans);
 }
 int gcd ( int a, int b ){
	int c;
	while ( a != 0 ) {
    		c = a; a = b%a;  b = c;
 	}
 	return b;
 }
 int calc2(int a1,int a2,int a3){
	int a4=a1*a2,a5=a4,ans=1;;
	while(a5%a3!=1){
		a5+=a4;
		ans++;
	}
	return ans;
 }
 int calc3(int a1,int b1,int a2,int b2,int a3,int b3){
	//a1,a2,a3は全て互いに素だと仮定。
	int k1=calc2(a1,a2,a3)*a1*a2*b3;
	int k2=calc2(a1,a3,a2)*a1*a3*b2;
	int k3=calc2(a2,a3,a1)*a2*a3*b1;
	int k4=k1+k2+k3;
	int k5=a1*a2*a3;
	k4%=k5;
	printf("問い6-5-3答え%d",k4);
 }
 int main(){
	calc(120);
	calc3(3,1,5,4,7,3);
 }