Hatena::Grouptopcoder

SRM diary(Sigmar)

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

2012-03-17SRM537 Div1

SRM537 Div1 275 KingXNewCurrency

| 03:57 | SRM537 Div1 275 KingXNewCurrency - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - SRM537 Div1 275 KingXNewCurrency - SRM diary(Sigmar) SRM537 Div1 275 KingXNewCurrency - SRM diary(Sigmar) のブックマークコメント

Problem Statement

コーディングフェーズ

よく分からんがmax(A, B)までの数iを候補として、適当にlcm(X, i)までの数で問題ないかチェックすればいいだろう

というのが正しそうかどうかを検討するのに20分くらい要した


後で

そもそもAとBをXとiで表せなければダメだし、逆にそれができれば他の数も全部表せるので、そのチェックだけで良かった

相変わらず不要な検討ばかりして時間がもったいない。。。


ソースコード

提出した版

ll gcd(ll a, ll b) {
	while(b) {
		a=a%b;
		swap(a, b);
	}
	return a;
}

ll lcm(ll a, ll b) {
	return a/gcd(a,b)*b;
}

class KingXNewCurrency {
public:
	int howMany(int A, int B, int X) {
		int res;
		
		if(A>B) swap(A, B);
		int g=gcd(A, B);
		if(g%X==0) return -1;

		res=0;
		for(int i=1; i<=B ;i++) {
			int g2=gcd(X, i);
			if(g%g2!=0) continue;
			int l2=lcm(X, i);
			int can[40010];
			memset(can, 0, sizeof(can));
			for(int j=0; X*j<=l2; j++) {
				for(int k=0; X*j+i*k<=l2; k++) {
					can[X*j+i*k]=1;
				}
			}
			bool ok=true;
			for(int j=0; A*j<=l2; j++) {
				for(int k=0; A*j+B*k<=l2; k++) {
					if(!can[A*j+B*k]) {
						ok=false;
						break;
					}
				}
				if(!ok) break;
			}
			if(ok) res++;
		}

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