Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2011-06-26TCO2011 Round2

TCO2011 Round2 250 GuessTheNumberGame

| 13:30 | TCO2011 Round2 250 GuessTheNumberGame - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - TCO2011 Round2 250 GuessTheNumberGame - SRM diary(Sigmar) TCO2011 Round2 250 GuessTheNumberGame - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

何これ むずい

いやしかし落ち着け。Easyからそんなに難しい問題が出るはずがない。

よく考えると、合成数がYだと必ずその因数もYになるはずだ

ということは、素数だけ考えればOKか!!

いや、違う

2がYでも4や8がYとは限らない

素数のべき乗を考えないといけない

まずエラトステネスの篩でnまでの素数を列挙して

各素数について、n以下で最大何乗までいけるか計算する

そしてその指数+1を解に掛けていけば、答えが出る

書いた

サンプル合った

提出

サンプルが非常に強固だから問題なさそう


ソースコード

vector <int> cpn(int n) {
	vector <int> vn(max(2, n+1), 1);

	vn[0]=vn[1]=0;
	for(int i=2; i*i<=n; i++) {
		if(!vn[i]) continue;
		for(int j=i*i; j<=n; j+=i) vn[j]=0;
	}
	
	return vn;
}

const int MOD= 1000000007;

class GuessTheNumberGame {
public:
	int possibleClues(int n) {
		int res=1;

		vector <int> vn=cpn(n);
		for(int i=2; i<=n; i++) {
			if(vn[i]) {
				ll v=i;
				while(v<=n) {
					v*=i;
					if(v>n) break;
					vn[i]++;
				}
				res=(ll)res*(vn[i]+1)%MOD;
			}
		}

		return res;
	}
};
トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20110626