ABC475 G - Has Many Divisors

考え方

まず、$D$ が無害な値である場合を考えてみる。

正の約数の個数は、素因数分解したときの指数に $1$ を足した数の総乗。
ということは、例えば $18$ や $600$ などは、考える意味がない。
なぜなら、$18=2^1\times 3^2$ と同じ個数を $12=2^2\times 3^1$ で表現できる。
$600=2^3\times 3^1\times 5^2$ も $360=2^3\times 3^2\times 5^1$ でよい。

ということで、指数が全て降順になっているものだけ探索すればよい。
$53$ 以下の素数の積が $10^{18}$ を超えるので、番兵を含めても $60$ より大きい素数は考えなくてよい。
各素数の指数を深さ優先探索で決めて、$N$ 以下に収まる範囲の、整数とその約数個数を列挙できる。

$D$ が無害な値というのは、$60$ より大きい素因数をもつ場合という意味。
この場合、$D$ の倍数でないという制約を無視しても、そもそも最善の値が $D$ の倍数にならない。

では、$D$ が小さい素因数ばかりの場合にはどうか。
例えば $D=600=2^3\times 3^1\times 5^2$ の場合。
$D$ の倍数でないようにするには、いずれかの指数が $D$ での指数より小さければよい。
つまり、以下の $4$ パターンを調べればよい。

• 全ての指数が降順になっているもので、$D$ の倍数であるものを除外する
• $2^2$ として、他の指数が降順になっているものを調べる
• $3^0$ として、他の指数が降順になっているものを調べる
• $5^1$ として、他の指数が降順になっているものを調べる

「$2^1$ として、他の指数が降順になっているものを調べる」などは調べる必要がない。
$3$ 以上の素数の指数に $2$ 以上のものがあれば、それを $1$ 減らして $2^2$ にしても約数が減らないからである。

ただし、途中の素数が飛ばされることがあるので、素因数として使う必要がある範囲が広がる。
$60$ までだと足りなくなることがあるので、$70$ 程度まで範囲に入れておく。

計算量の推定は難しい。
とはいえ、列挙する数が $10^7$ 個を超えることはなさそうなので、$10$ ケース分やっても間に合う。

具体例での動作

次の場合を考える。

n: 25
d: 12

$D=12=2^2\times3^1$ なので、以下の $3$ 種類の探索をする。

• 通常の探索
• $2$ の指数を $1$ に固定する探索
• $3$ の指数を $0$ に固定する探索

まず、全ての指数が降順になっているものを探索する。
$25$ 以下で列挙される候補は次の通り。

$12,24$ は除外されるので、この探索での最善は $16$ となる。

次に、$D$ の素因数ごとに、その指数を $D$ での指数より $1$ 小さく固定して探索する。

$2$ の指数を $1$ に固定した場合、$3$ 以降の指数を降順にすると次の候補が列挙される。

この探索での最善は $18$ となる。

$3$ の指数を $0$ に固定した場合、$3$ を飛ばし、残りの素数の指数を降順にすると次の候補が列挙される。

この探索での最善は $20$ となる。

以上より、各探索での最善は $16,18,20$ である。
約数個数の最大値は $6$ 個で、$18$ と $20$ が並ぶ。
そのいずれかを答えればよい。

注意点

$N$ や探索中の整数は int 型からはみ出る。
long long 型を用いること。

別解

特になし。