08-31 HDU_Steps2.1 HDU1108 HDU2138 HDU1713 HDU1722 HDU2136 HDU2504 HDU1286 HDU1717

HDU_Steps2.1問題を解く
2.1.1 HDU 1108最小公倍数如題、a*b/gcd(a,b)でよい
2.1.2  HDU2138 How Many Primes Numbers
直接判断はタイムアウトし、直接打表のスペースが足りないため、部分打表、部分判断の方法を採用した.
ランダム素数テストの方法があるようですが、上記の方法は簡単ではありません.

#include <cstdio>
#include <string>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
#define MAXN 10000000
using namespace std;
bool prime[MAXN];
int isp(int x){// 
	int k=(int)sqrt(x);
	for(int i=2;i<=k;i++)if(x%i==0)return 0;
	return 1; 
}
void init(){// 
	prime[1]=1;
	for(int i=2;i<MAXN;i++){
		if(prime[i])continue;
		for(int j=i*2;j<MAXN;j+=i){
			prime[j]=1;	
		}	
	}
}
int main(){
	int n,a; 
	init();
	while(scanf("%d",&n)!=EOF){
		int r=0;
		while(n--){
			scanf("%d",&a);	
			if(a<MAXN)r+=(prime[a]?0:1);
			else r+=isp(a);
		}
		printf("%d
",r);
	} 
	

    //system("pause");
    return 0;
}

2.1.3 HDU 1713出会い周期
長いことやっと問題の意味を理解して、もとは2つの点数の最小の公倍数を求めます.まず通分し(便宜上、直接2つの分母の積を公倍数の分母とする)、それから分子の最小公倍数が最も公倍数の分子を求めて、最後に約分すればいいので、分母が1であれば整数を出力します

#include <cstdio>
#include <string>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef __int64 LL;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
int main(){
	int cas;
	LL fz1,fz2,fm1,fm2,fz,fm;
	scanf("%d",&cas);
	while(cas--){
		scanf("%I64d/%I64d%I64d/%I64d",&fz1,&fm1,&fz2,&fm2);	
		fz1*=fm2,fz2*=fm1;
		fm=fm1*fm2;
		LL fz=fz1/gcd(fz1,fz2)*fz2;
		LL gc2=gcd(fz,fm);
		fz/=gc2,fm/=gc2; 
		if(fm!=1)printf("%I64d/%I64d
",fz,fm);
		else printf("%I64d
",fz/fm);
	}
    //system("pause");
    return 0;
}

2.1.4 HDU 1722 Cake a+b-GCD(a,b)GCD(a,b)は重ね合わせた刃数の数である
2.1.5 HDU 2136 Largest Prime Factorはこの数の最大素数を取り除くことができることを求めて何番目です
素数ふるい法の柔軟な運用、後の優先は新しくて、最後に数えるべき位置の上で残す数に対して最大の素数(いくつ目)です

#include <cstdio>
#include <cmath> 
#include <algorithm>
#include <cstdlib>
#include <string.h> 
using namespace std;
int pri[1000001],n,ps;
int main(){
	memset(pri,0,sizeof pri);
	pri[1]=0,ps=0;
	for(int i=2;i<=1000000;i++){
		if(pri[i])continue;
		ps++;// 
		for(int j=i;j<=1000000;j+=i){
			pri[j]=ps;	
		}
	}
	while(scanf("%d",&n)!=EOF){	
		printf("%d
",pri[n]);
	}
	return 0;	
}

2.1.6 HDU 2504またGCDを参照
a,cの最大公約数はbであり,a,bが最小cを求めることが知られており,b!=c
最初は2倍bだと思っていたが、そうではなかった.このようにa,cの最大公約数はbではなくcである可能性がある.正しい方法は2*bから列挙し、GCD(a,k*b)=bになるまでbを順番に加え、c=k*bになる.
2.1.7 HDU 1286新しい友達を探して、裸のオラの関数、直接テンプレートをたたく
2.1.8 HDU 1717小数点2純小数点回転数
有限小数、例えば0.53直接53/100を約分可能に約分する
循環小数の場合、例えば0.(53)  ==> 0.(53)*100=53.(53)  ==>  53.(53)-0.(53)=53=>すなわち(100-1)*0.(53)=53 ==>53/99
混合サイクル例0.3(53)=>0.3(53)*1000-0.3(53)*10=353.(53)-3.(53)=350=>すなわち(1000-10)*0.3(53)=350=>350/990

#include <cstdio>
#include <string>
#include <math.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
double gcd(double a,double b){return b==0?a:gcd(b,(int)a%(int)b);}
int main(){
	int cas;
	char line[20]; 
	
	scanf("%d",&cas);
	while(cas--){
		scanf("%s",line);
		double d1=0,d2=0,fz,fm;// , , , 
			
		int ll=0,rl=0,pos;// 
		for(pos=2;pos<strlen(line)&&line[pos]!='(';pos++)d1=d1*10+line[pos]-'0',ll++; 
		for(pos++;pos<strlen(line)&&line[pos]!=')';pos++)d2=d2*10+line[pos]-'0',rl++;
		
		if(strchr(line,'(')-line>=0){// 
			fz=d1*pow(10,rl)+d2-d1;
			fm=pow(10,ll+rl)-pow(10,ll);
		}else{
			fz=d1;
			fm=pow(10,ll);	
		}
		
		LL gc=gcd(fz,fm);
		printf("%.0lf/%.0lf
",fz/gc,fm/gc); 
	}
    //system("pause");
    return 0;
}