ARC 160

Sun, Jul 20, 2025

A. Reverse and Count

https://atcoder.jp/contests/arc160/tasks/arc160_a

B. Triple Pair

https://atcoder.jp/contests/arc160/tasks/arc160_b

解説 AC.

解説の解説。

https://atcoder.jp/contests/arc160/editorial/6355 で出てくる $3 \times \sum_{i=M+1}^N \floor{N/i}^2$ の計算部分について($M = \floor{\sqrt{N}}$)。愚直に for loop すると TLE する。この区間の中に $\floor{N/i}$ の種類は $O(\sqrt{N})$ 種類あるが、 $\floor{N/i} = \floor{N/j}, (i \neq j)$ となることがあるので同じ値を取るものがいくつあるかを数える必要がある。

整数 $t$ に対して $t = \floor{N/i} \in [1, \sqrt{N})$ となる $i$ の範囲について考える。

\begin{align*} &t = \floor{N/i} \\ \Leftrightarrow &t \leq \frac{N}{i} < t + 1 \\ \Leftrightarrow &\frac{1}{t + 1} < i/N \leq \frac{1}{t} \\ \Leftrightarrow &\frac{N}{t + 1} < i \leq \frac{N}{t} \\ \Leftrightarrow &\floor{\frac{N}{t + 1}} + 1 \leq i \leq \floor{\frac{N}{t}} \end{align*}

$\floor{N/(t+1)} + 1 = M$ のとき、$i \geq M+1$ であることに反するので無視する。

それ以外のときは $\floor{N/t} - (\floor{N/(t+1)}+1) - 1$.

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    using Int = unsigned long long int;

    auto kth_root = [](Int x, Int k) -> Int {
        assert(k != 0);
        if (x == 1 || k == 1) return x;
        Int l = 0, r = x;
        while (r - l > 1) {
            Int m = (r - l) / 2 + l;
            Int t = x;
            rep(i, k) t /= m;
            if (1 > t) {
                r = m;
            } else {
                l = m;
            }
        }
        return l;
    };

    // 平方根
    auto isqrt = [&](Int x) -> Int {
        return kth_root(x, 2);
    };

    auto cal = [&]() -> void {
        ll N;
        cin >> N;

        ll M = isqrt(N);

        mint ans = M * M * M;
        for (ll t = 1; t * t < N; t++) {
            ll l = N / (t + 1) + 1;
            if (l == M) continue;
            ll r = N / t;
            ans += 3ll * (r - l + 1) * t * t;
        }
        cout << ans.val() << '\n';
    };

    int t;
    cin >> t;
    rep(i, t) cal();
}