SRM517 Div1 250

とぷこだ 過去問

問題

ある整数Nとtargetが与えられる。
整数xをもしy*z==xとなるy,z(>=2)に分解できるとき、xはyとzに分解することができる。
整数Nを上記のように分解していったときに、常にtargetの数値が出てくる場合は"Yes"、そうでない場合は"No"を返せ。

例えば、N=12,target=6の場合は、
12->(2,6)->ok
12->(3,4)->ng
なので、"No"を返す。N=8,target=4の場合は、
8->(2,4)->ok
8->(4,2)->ok
なので、"Yes"を返す。

考え方

素直にメモ化dfs。

ある整数xを分解すると常にtargetの数値出てくる場合true、そうでない場合falseを返す関数dfs(int x)を考える。
2以上x/2未満でxの約数となるすべての整数mについて、dfs(m)またはdfs(x/m)のどちらかがtrueであればxもtrueとなる。
整数xのdfsの結果をメモすれば間に合う。

反省

素因数分解したりよくわからない法則を探すよりも素直に探索してみて間に合うか検討してみること。