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までの数をそれぞれ素因数分解し、それぞ…

問題リンク 解法 a,b,cのなかにKが持っていない素因数を持っている数が含まれることはないので、a,b,cは必ずKの約数だとわかる。 後は約数の中から条件を満たす組を全探索できれば良いが、最大5000個以上の約数を持つ可能性があるのでN3では間に合わない。 (…