SRM 643 Div1 Easy - TheKingsFactorization
問題
TopCoder Statistics - Problem Statement
問題概要
自然数の素因数分解を求めよ。ただし、
の素因数の小さい方から順に奇数番目だけ素因数が何であるかのヒントが与えられる。
例えば、であるとき、素因数分解は
であるから、小さい方から数えて奇数番目の
がヒントとして与えられる。
アイデア
普通に素因数分解するのでは、かかってしまうので、間に合わない。そこで、ヒントを利用する。
まず、ヒントとして与えられる素因数の個数で、全体の素因数が何個あるかの見当を付けることが出来る。例えば、ヒントが2個なら、答えには3個か4個の素因数があるはずである。
ヒントの個数が1個なら、答えに含まれる素因数の個数は1個か2個ということになる。これはヒントをみればどちらになるか簡単に判断できて、その1個がと一致するなら素因数は1個で、そうでないなら
をそのヒントで割った値も素因数になっていることが確定する。
以下、ヒントの個数が2個以上である状況を考える。まず、を既にわかっている素因数で割っておく。
まず、素因数分解の素朴な方法として、最初に述べた計算量からも推測がつく通りに対する素因数分解は
から
までのそれぞれで割れるかどうかを試すという方法がある。それぞれの数で順番に
を割っていき、終わった時点で
が1よりも大きければその数も(
より大きい)素因数であるといえる。
これだけだと間に合わないが、ここでヒントを利用する。ヒントの中で一番大きい数に注目する。すると、ヒントの与えられ方の性質から、
以上の素因数は多くとも1つしかないことが分かる。よって、
を試し割りするのはこの
以下で十分である事がわかる。
がとても大きい数だったらこの制約は意味がないじゃないかと思うかもしれないが、直感的には
が大きいような状況では、既に
が
で割られているので
が十分小さくなるというイメージで計算が間に合う。
最悪の状況を考えてみると、実際に素因数が3個である状況を考え、与えられるヒントが2とだったとする。この時に、2つの制約
と
がちょうど拮抗する状況を考えても、
であるから試し割りの範囲は最悪でも
くらいに収まることが分かる。
とても面白い問題だった。
実装(C++)
続きを読むCF 701 F - Break Up
問題
問題概要
頂点
辺の無向グラフがある。グラフが連結である保証はない。
いま、ある辺を削除して頂点から頂点
への移動をできなくなるようにすることを考える。しかし、辺の削除の上限は2本である。辺にはそれぞれ削除のコストがついている(
とする)ので、削除のコストが最小になるように削除した時の、そのコストと、その時に削除する辺はどれになるかを答えよ。ただし、不可能な場合には-1とだけ答えよ。
アイデア
まず、もとのグラフでと
がもともと繋がっていなければ答えは0になる。以下、つながっている場合を考える。
もし、1つの辺の削除によってと
を連結でなくすることが可能なら、その辺は
から
へのあらゆるパスに含まれることになる。よって、二重辺連結成分分解によって橋をみつけて、
から
へのある1つのパス上を眺めてそのパス上にある橋のコストをみていけば良い。
2つの辺を削除してと
の連結を切ることを考えるとき、削除する辺のうちの1つは見つかった1つのパス上になければならない(でないとそのパスを使うことが出来るから)。パス上のある辺
を削除したと考えると、この1つの辺を削除したグラフに対して橋を見つけて、あるパス上の橋を削除すべきということになる。
このいずれでも不可能な時は-1と答えることになる。
