atcoder.jp 解法 次のように定義する。 操作1、N が K で割り切れるとき、N を N/K に置き換える 操作2、そうでないとき、N を N−K に置き換える 場合分けして考える。 操作2だけでNを1にできるような数 これは、N-1の1以外の約数すべてが該当する。 理由 m…

atcoder.jp 解法 N!の約数を順に列挙していこうとすると、N次第ではN!がとてつもなく大きい数になってしまうため、現実的ではない。 そこで、約数を素因数を組み合わせた結果と考えることにする。 具体的には、1 ~ Nまでの数をそれぞれ素因数分解し、それぞ…

atcoder.jp 解法 $ A_i B_i $はなるべく小さい方が数列Bの総和は小さくなる。 数列Aの要素にそれぞれ適当な値をかけて、全て同じ値を作り出したいのだから、$ A_i B_i $は数列Aの要素の最小公倍数にすると最小になることがわかる。 最小公倍数はとんでもなく…

atcoder.jp ※なぜかmathjaxでK-1を下付き文字として表示できないので、この記事ではK=Aとします。 $ X_{i-1} $ は正しく表示されるのに、$ X_{K-1} $ はなぜかうまくいきませんでした。 原因不明です。 解法 数列の要素が答えにどれだけ影響を及ぼすか、とい…

問題リンク 解法 問題文を読んだだけでは、観覧車がどのような動きをしているのかわかりにくいが、図を書いてみると、中心を(0, 0, L/2)とした半径2/Lの円周上を動いていることがわかる。 まず、与えられた時間の時の現在地の座標が知りたい。 中心を(0, 0, …