kojingharangの日記

SRM 611 Div1 250 LCMSet

21:26 |

• 数列 A, B が与えられる。"Aの任意の部分集合のLCM"の集合 と "Bの任意の部分集合のLCM"の集合 が等しいかどうかを求めよ。
• |A|≦50, |B|≦50, 数字≦10^9

(しばらく)

• 素因数分解したとしてサンプル1を考えてみる
• こんな感じの図(右上)を唸りながら大量に書く（キケン）
• LCM は和集合をとることに相当する
• ならば、数列のうち、数列の他の数字から作れるもの("OR"しても変わんないもの)を消して、根源的なものだけ残してみる。
• それらを比べて同じなら同じ、異なるなら異なる、でいい気がする

• 数列にある数字それぞれについて、ほかのやつすべてと比べてごにょごにょして判定するのだろうか
• と考えてたらいつの間にか「ソートしといて今までの max を持っておいてある数字が max からはみ出たら根源的」でいいんじゃね、となる
• 素因数分解して (素数の配列, 指数の配列)の配列 を作ってめんどくさいコードで比較

• system test failed

• いままでの max と比較、だと 5, 6, 15 みたいなときに 15 を根源的じゃないと判定してしまうようだ。

5 = 2^0 * 3^0 * 5^1 を 5 : 0 0 1 と表すと

5  : 0 0 1
6  : 1 1 0
15 : 0 1 1  // 5, 6 からは作れないので根源的とすべきだがそう判定されない

• うむーなるほど。他のやつが含まれるなら和集合をとっていって、その数にならなければ根源的、とすれば良いようだ。

• accepted in practice room

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

set<int> h(vector<int>& A) {
	set<int> s;
	REP(i, A.size()) {
		ll l = 1;
		REP(j, A.size()) {
			if(A[j]<A[i] && lcm(A[i], A[j])==A[i]) l=lcm(l, A[j]);
		}
		if(l < A[i]) s.insert(A[i]);
	}
	return s;
}

class LCMSet {
	public:
	string equal(vector <int> A, vector <int> B) {
		return h(A)==h(B) ? "Equal":"Not equal";
	}
};

ツイートする