値を列挙した配列を作成する。個これを列挙した全素数で繰り返す。]残っている2以上の数は素数である。超過してしまい矛盾する。この中で要素毎にカウントを取れば、残りの素因数とその個数もわかる。場合は同じ素数が残る場合がある点に注意。しておけば、残る素数は必ず重複しなくなる。区間にも同じことをやれば答えが求まる。2つの数字で表すのは冗長なので、説明上は以下のように番号を振りなおす。その全辺を一筆書きでなぞれるルート(オイラー閉路)を構築すればよい。ルート構築は、そのようなグラフが作れたなら必ず出来る。有向オイラー閉路の条件が、「頂点の入次数=出次数」が全頂点について満たされるかなので。本の辺が、隣接マスの0、2、4にそれぞれ何本ずつ向かうか、というのを各マスについて決めたい。これは最大流で解ける。本の辺が出た、無向連結グラフ」でもよい。「各頂点から偶数本の辺が出た無向グラフ」でも必ずオイラー閉路を作れるし、その一例の構築方法も大きく変わらない。その場合、グリッドが二部グラフであることを利用し、もう少し最大流を解くグラフを簡潔にできる。総和分流せなければ不可能。流せたら、流し終わった後のネットワークに、どの辺にどれだけ流したかの情報が残っている。0→1に流量5を流していれば、目標の連結グラフでは0を出て1に入る辺を5本作ればよいことになる。最大流に任せると連結性が保証されない。⇅6⇄7⇄8あらかじめ、外周をぐるっと1回だけループさせると決めうてばよい。↓6←7←8各辺をこの向きに最低1回使うというのが重要で、実際に通る順番はバラバラでよい。4は必ず1357のどれかと接続されるため、これで連結性は保証される。どのような成立状態でも上手く辺の結び方と方向を変えることで、外周一周を使う成立状態に変換可能である。0→1を代わりに使う形に変換できないものを考え、それが存在しないことを示す。グリッドの回転・反転、辺の向きの一斉反転を使えば、この1箇所だけ証明できれば十分。以下のような図を使って、使わないことが確定した辺、使うことが確定した辺を決めていく。各頂点の入出次数を変えてはいけない連結でなくなってはいけない既に存在する、他の外周辺1→2や2→5などを代わりに失ってはいけない以上を守って辺を変えても、0→1を使うようにできないものを考える。1→0を通って1に戻る、交差しない閉路が必ず存在する。それを全て反転させることで0→1の辺を作れる。反時計回りを時計回りに変換するので、他の外周辺を失うことはない。←よって、1→0の辺も使えないことがわかる。3→0の辺を使うことが確定する。3→0を使うことが確定しているため、連結は保たれる。同様に、こう繋ぎ替えられる。先ほどの、閉路の辺反転を使うことで、0→1の辺を作れる。一時的に外周辺3→0を失うが、これを含めて辺反転させればよい。よって、1→4、4→1の辺も使えないとなる。すると、1を他と連結にするためには、2、5と連結するしか無くなる。以下、同様の議論が4⇄5にも適用され、これらの辺も使えないとなる。すると5は連結を保つため、8、7と連結になる。辺も使えなくなり、4が孤立する。流すと決める全域木を全探索したり、ランダムでフローの流し方を何通りか試す方が考察は速そう。各頂点間の辺数が決まったら、あとはオイラー閉路の構築となる。これは、DFSの帰りがけ順で通過頂点を記録するとよい。perogram同じ頂点間に辺が複数本あり、頂点ではなく辺について網羅しないといけないため、よくあるDFSとは若干コードが異なる点に注意。複数本無ければ点と辺を逆転させて考える手もありだが、複数本ある場合は辺の数が大量にできてしまう。通りの辺を張らないといけない?解法2答えの1つには外周を一周するものが必ず存在するとわかったので、それをベースとしてもよい。回)は最大流で求められる。すると、オイラー閉路の構築が楽になる。ikatakosメディアマネージャー文書の先頭へ。