余りの処理 - c21coterie @ ウィキ

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

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