LCMとGCM - c21coterie @ ウィキ

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

問い３-1

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

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

問い3-１-２

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

#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);
}

問い３-２

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

#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とｄｙは既約であると仮定。
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とｂの最大公約数が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);
}

問い３-３-２
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

問い１　A+B=720,gcd(A,B)=24であるA、Bの組
問い２　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問い３-4-２\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);
}