。をの素因数の集合とする。 が答え。 とは互いに素なので両方が、の素因数の倍数であることはない。 またがの倍数なのでがの倍数の場合、もの倍数。 よってとは共にの倍数ではない。 以上からとにある数を足すことで両方をの倍数にできる。 のすべての素因数にたいしてこの足す数の最小値が答え。 注意点1。 のとき出力する答えは。「差が1の2数は互いに素 gcd(x,y)=1」は有名事実。いくつ足してもとの差は1のままなので、永遠に互いに素。 注意点2。 上の考察を素直に実装するとTLEになる。素朴に高速化するとMLEになった。いい感じに実装する必要がある。 イメージ図