AOJ再挑戦問5～9 - c21coterie @ ウィキ

問5　GCD and LCM

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0005&lang=jp
2つの整数の最小公倍数と最大公約数を出力する問題。

解法

公式通りgcdとlcmを計算するだけです。

#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(){
	int g,a,b;
	while(scanf("%d %d",&a,&b)!=EOF){
	g=gcd(a,b);
	printf("%d %d\n",g,a*(b/g));
	}
}

問6　Reverse Sequence

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0006&lang=jp
読み込んだ文字列を逆順に表示するプログラムをかけ。

解法

文字列を逆順に表示するだけです。

#include<stdio.h>
#include <string.h>
int main(){
 	char str[21];
	scanf("%s",str);
	for(int i=strlen(str)-1;i>=0;i--)printf("%c",str[i]);
	printf("\n");
}

問7 Debt Hell

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0007
複利借金の額を計算する問題。
解法
整数型で計算しても問題ありません。
1000以下があれば自動で切り上げるだけです。

#include<stdio.h> 
int main(){
	int n,m=100000;
	scanf("%d",&n);
	while(n--){
 		m*=1.05;
		if(m%1000>0){
			m+=1000-(m%1000);
		}
	}
	printf("%d\n",m);
}

問8　Sum of 4 Integers

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0008&lang=jp
0～9の数を4つ足してできる数字の作り方の組み合わせ数を求める問題。

解法
最初に全部の場合の答えを初歩的な動的計画法で求めます。
計算量は大差ないので4重ループで求めてもよいでしょう。

#include<stdio.h>
int main(){
int ans[51]={0},n;
ans[0]=1;
for(int i=0;i<4;i++){
	for(int k=36;k>=0;k--){	
		for(int j=1;j<=9 && k-j>=0;j++){
			ans[k]+=ans[k-j];
		}
	}
}

	while(scanf("%d",&n)!=EOF){
	printf("%d\n",ans[n]);
}
}

問9　Prime Number

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0009&lang=jp
指定された数ｎ以下の素数の個数をこたえる問題。

解法
篩で選り分けてあとは下からカウントするだけです。
count配列のメモリ使用量がもったいない感じですがあまり気にしません。

#include<stdio.h>
#include<math.h>
#include<string.h>

const int limit=1000001;
bool is_prime[limit];
int  count[limit]={0};
 
void calc(){
	//エラトステネスの篩
	memset(is_prime,true,sizeof(is_prime));
 	is_prime[0]=is_prime[1]=false;
	for(int i=2;i<=sqrt(limit);i++){
		if(is_prime[i]==false)continue;
		for(int j=i*2;j<limit;j+=i){
			is_prime[j]=false;
		}
	}
	
 	//素数の個数のカウント
	for(int i=1;i<limit;i++){
		count[i]=count[i-1]+is_prime[i];
	}
	
}
int main(){
	int n;
 	calc();
  	while(scanf("%d",&n)!=EOF){
		printf("%d\n",count[n]);
	}
}