391.1
GCDセット。
500
箱がN個ある。それぞれに鍵がかかっていて、中には鍵が一つ入っている。鍵はN個の箱のどれかの鍵を開けることができるもので、同じ鍵はない。M回だけ箱をこじ開けてよいとき、全部の箱を開けられる確率を求めよ、という問題。
要は箱をこじ開けたときに、こじ開けた箱と同じ鍵が出てくるまで何個箱を開けられるか、という部分の確率を求めつつ、部分問題に落としていくだけ。確率は分数で求めないといけないので、適切にGCDを計算してやる必要がある。
1000
整数配列が与えられるので、全部の最小公倍数が変わらないようにしつつ、できるだけ前から順に小さい値に書き換わるように、各値に対して除算を行いたい。最終的な結果を答えよ、という問題。
全部の素数を求めて、一番その素数で割り切れる回数が大きい(同じなら後ろの)要素以外をその素数で割ってやれば良い。ただし、そうすると10^9未満の素数を全部考慮しないといけなくなるために終わらない。取り敢えず10^6未満の素数についてであれば現実的な時間で終わるので、それを先にやっておく。すると、残った整数配列の各要素の組について、GCDを計算してやると、素数または素数の積という形が得られるが、ここで、10^6未満の素数は登場しないことから、高々二つの素数の積しか登場しないことが分かる。なので、これを素数とみなして同様の処理をしてやっても問題にならない。後はこれで登場する素数または素数の積がいなくなるまで繰り返せば良い。(p*qが登場した関係で、p*pのpが欠けてしまっておかしなことになるためには、p*p*qで割り切れるものが存在しないといけないが、これは3つの10^6以上の素数の積なので、この問題では登場しない。)
