「AOJ再挑戦51~55」の編集履歴(バックアップ)一覧に戻る

AOJ再挑戦51~55 - (2014/01/29 (水) 22:52:12) のソース

*問51 Differential II
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0051
数字の文字列を並べ変えて最大の数と最小の数を作った時その差を計算する問題。
解法
並べ替えて手前と後ろから数字に直すだけです。

 #include<stdio.h>
 #include<algorithm>
 
 int main(){
 	int n;
 	char text[9];
 	scanf("%d",&n);
  	while(n--){
 		int max=0,min=0;
 		scanf("%s",text);
 		std::sort(text,text+8);
 		for(int i=0;i<8;i++) min=min*10+text[i]-'0';
  		for(int i=7;i>=0;i--)max=max*10+text[i]-'0';
 		printf("%d\n",max-min);
 	}
 }




*問52 Factorial II
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0052
20億!とかの末尾の0の数をこたえる問題。

解法
10^nの素因数は2と5で5の数で5のほうが少ないです。
5,5^2、5^3、、、が何個できるかを集計すれば答えが出ます。

 #include<stdio.h>
 #include<iostream>
 
 int main(){
 	long long int n;
  	while(std::cin>>n){
 		if(n==0)break;
 		long long int ans=0,fivePow=5,n1=n;
 		while(n1>=fivePow){
  			ans+=n1/fivePow;
 			fivePow*=5;
 		}
  		std::cout<<ans<<"\n";
 	}
 }




*問53 Sum of Prime Numbers
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0053
下からn個めまでの素数を足したものをこたえる問題。
解法
篩で求めて下から集計してテーブル化するだけです。

 #include<stdio.h>
 #include<vector>
 #include<string.h>
 const int MAX=105000;
 bool isPrime[MAX];
 
 void calc(){
 	memset(isPrime,true,sizeof(isPrime));
 	isPrime[0]=isPrime[1]=false;
 	for(int i=2;i*i<=MAX;i+=(1+(i&1))){
 		if(isPrime[i]==false)continue;
  		int add=i%2==0?i:i*2;
 		for(int j=(i%2==0?i*2:i*3);j<=MAX;j+=add){
  			isPrime[j]=false;
 		}
 	}
 }
  
 int main(){
  	calc();
 	int sum=0;
 	std::vector<int> memo;
 	memo.push_back(0);
 	for(int i=2;i<MAX&&memo.size()<=10000;i++){
 		if(isPrime[i]){
 			sum+=i;
  			memo.push_back(sum);
 		}
 	}
 	int n;
 	while(scanf("%d",&n)!=EOF){
  		if(n==0)break;
 		printf("%d\n",memo[n]);
 	}
 }