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

問い3-1

175/24と33/140でわっても自然数となる最小の既約分数。

代入される分数は既約であると仮定。

問い3-1-2

12cm、8cm、18cmの積木を10000個同じ方向に並べて立方体を作るとき何センチの立方体が作れるか。
使わない立方体があってもよい。


#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 a1,int a2, int b1,int b2){
// a1/a2 b1/b2
int k=gcd(a2,b1);
int c1=a2*(b1/k);
int c2=gcd(a1,b2);
k=gcd(c1,c2);
printf("%d/%d\n",c1/k,c2/k);
}
void calc2(int a,int b,int c,int size){
int k=a*(b/gcd(a,b));
int q=k*(c/gcd(k,c));
printf("%d",q);
int s=q/a*q/b*q/c,x;
printf(" %d",s);
for(x=1;x*x*x*s<size;x++);
x--;
printf(" %d",(x*q));
}
int main(){
calc(175,24,33,140);
calc2(12,8,18,10000);
}







問い3-2

長方形の頂点から入った光が長方形内で反射し何回の反射で頂点~でていくか答える問題。


#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 h,int w,int dx,int dy){
//dxとdyは既約であると仮定。
int k=gcd(w,dx);
int s=(w*dx/k)/dx-1;
int len=w*dx/k;
s+=len/w-1;
printf("%d",s);
}
int main(){
calc(42,60,21,42);
}




問い3-3

aとbの最大公約数が6、最小公倍数は216の時条件を満たすa,bの組の個数を数える問題.


#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 c=b/a;
for(int d=1;d*d<c;d++){
	if(c%d==0&&gcd(d,c/d)==1){
		printf("(%d %d)",d,c/d);
	}
}
}
int main(){
calc(6,216);
}


問い3-3-2
a<b<cかつa,b,cの最小公倍数は216最大公約数は12.
この条件を満たすa,b,cの組を答えよ。

#include<stdio.h>
//計算量の関係で小さい値でしか検証できない手抜き実装
//sqrt(u)やu^1/3までしか検証しないとすれば少し早くなる。
void calc(int m,int n){
int u=n/m;
for(int a=1;a<u;a++){
	if(u%a!=0)continue;
	for(int b=a+1;b<u;b++){
		if(u%b!=0||u/b<=b)continue;
		for(int c=b+1;c<=u;c++){
			if(u%c!=0)continue;
			printf("%d %d %d\n",u*a,u*b,u*c);
		}
	}
}
}
int main(){
calc(12,216);
}








問い3-4

問い1 A+B=720,gcd(A,B)=24であるA、Bの組
問い2 AB=3888 最大公約数216となるA、Bの組

#include<stdio.h>
int gcd ( int a, int b ){
int c;
while ( a != 0 ) {
	c = a; a = b%a;  b = c;
}
return b;
}
void calc1(int a,int b){
int c=a/b;
for(int i=1;i<=c/2;i++){
	if(gcd(i,c-i)==1)printf("%d %d\n",b*i,b*(c-i));
}
printf("\n問い3-4-2\n");
}
void calc2(int a,int b){
int B=b/(a/b);
for(int i=1;i<=B;i++){
	if(B%i==0&&gcd(i,B/i)==1)printf("%d %d\n",a/b*i,a/b*B/i);
}
}
int main(){
calc1(720,24);
calc2(3888,216);
}