【AtCoder】ABC 480 E - Product-Bounded Arithmetic Sequences

2026-10-20

AtCoder/ABC/E問題 AtCoder/ABC/450点問題 AtCoder/水Diff AtCoder/NoviSteps/1D AtCoder/数学/等差数列 AtCoder/二分探索競技プログラミング

E - Product-Bounded Arithmetic Sequences

E - Product-Bounded Arithmetic Sequences

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

実行時間制限: 2 sec / メモリ制限: 1024 MiB / Difficulty: 1355 / NoviSteps: 1D / 配点: 450 点

問題概要

以下の条件を全て満たす正整数列 $A=(A_1,\dots,A_{|A|})$ を良い数列と定める。

$|A|\geq 3$
$A$ は等差数列である。
$A_2-A_1 > 0$

良い数列のうち、要素の総積が $N$ 以下であるものの個数を求めよ。なお、制約の条件下で答えが $10^{18}$ 以下となることが証明できる。

制約

$1 \leq N \leq 10^{18}$
$N$ は整数

考察

一見 $N$ が大きすぎてどうしようもなさそうだが、実は、数列の長さ $k$ が長くなるほど、条件を満たす初項 $a$ と公差 $d$ の組み合わせは急激に減少していく。

例えば、 $k = 3$ の場合、

a(a + d)(a + 2d) \leq N

を満たす組 $(a, d)$ の個数を数えればよい。

このとき、 $d \geq 1$ より $a^3 \leq N$ が必要で、 $1 \leq a \leq \sqrt[3]{N} \leq 10^{6}$ の範囲の整数 $a$ が探索対象になる。

さらに、 $a$ を固定すれば総積は $d$ に関して単調増加するため、二分探索で条件を満たす最大の $d$ を求めることができる。

これを一般化すると、長さ $k$ の数列に対して、初項 $a$ の探索範囲は $1 \leq a \leq \sqrt[k]{N}$ であり、 $a$ を固定すれば二分探索で条件を満たす最大の公差 $d$ を求めることができる。

また、初項・公差がともに 1 の場合が積を最小にするので、

1 \times 2 \times 3 \times \cdots \times k = k! \leq N

を満たす $k$ だけ調べれば十分。

$20! \approx 2.43 \times 10^{18}$ なので、 $k < 20$ まで調べればよい。

最後に計算量について。

長さ $k$ の数列について、初項は高々 $N^{\frac{1}{k}}$ 通り、二分探索は $O(\log N)$ 回、それぞれの判定に $O(k)$ 時間がかかる。

したがって、全体としては、

O\left(\sum_{k=3}^{20}kN^{\frac{1}{k}}\log N\right) = O(N^{\frac{1}{3}}\log N)

となり、本問の制約下では十分高速である。

実装例

1.#include <bits/stdc++.h>
2.using namespace std;
3. 
4.#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)
5.#define repe(i, start, end) for (auto i = (start); (i) <= (end); (i)++)
6. 
7.constexpr long long INFL = 1e+18;
8. 
9.using ll = long long;
10. 
11.// ======================================== //
12. 
13.int main()
14.{
15.    ll N;
16.    cin >> N;
17. 
18.    auto check = [&](ll a, ll d, ll l) -> bool {
19.        ll prod = 1;
20.        rep(i, 0, l) {
21.            ll next = a + i * d;
22.            if (next > N / prod) return false;
23. 
24.            prod *= next;
25.        }
26. 
27.        return true;
28.        };
29. 
30.    ll ans = 0;
31.    repe(l, 3, 20) {
32.        for (ll a = 1; check(a, 1, l); a++) {
33.            ll ok = 1, ng = INFL;
34.            while (ng - ok > 1) {
35.                ll mid = (ok + ng) / 2;
36.                if (check(a, mid, l)) ok = mid;
37.                else ng = mid;
38.            }
39. 
40.            ans += ok;
41.        }
42.    }
43. 
44.    cout << ans << endl;
45. 
46.    return 0;
47.}

https://atcoder.jp/contests/abc480/submissions/80170293

実装時間: 40分

コメント

$k$ が小さい場合で実験してみると、意外と途方もない問題ではないことが分かって拍子抜け。