hotpepsiの練習帳

SRM 611

math | 01:40

Div1 Easy (250) LCMSet

問題

• 集合Sが与えられる
• Sの全要素の最小公倍数をlcm(S)とする
• Sの全ての部分集合のlcmの集合をLCM(S)とする
• AとBが与えられる
• LCM(A)とLCM(B)が等しいかどうかを求める

方針

• Challenge Succeeded
• BにAの1要素aが含まれていないときは、Bの部分集合からaを作れる必要がある(逆も)
• Bの要素のうち、aの約数になっているもののLCMを取っていって、結果がaと等しいなら、aが作れる。作れないなら、等しくない
• Aの任意の部分集合について考える
• Aの任意の要素p,qについて、pとqそれぞれはBの部分集合で作ることができる。LCMについては、素因数単位で考えると乗数の最大値を取ったものであり、Bの同じ要素を2回以上使う必要はないので、LCMについても作ることができる。つまり任意の部分集合のLCMが作れる
• なので、要素を作れるかどうかだけ判定すればよい
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_611/LCMSet.cpp

結果

x-- 0pt 341st/644 rating 1257 -> 1247 (-10)

なぜ要素が作れるかどうかだけで判定できるのか理解するのに時間がかかった。

http://togetter.com/li/637876