題解：2020 NPSC 初賽 pA（數論分塊）

TOI 初選倒數 15 天，今天戳了一題滿有趣的題目，想記錄一下這題的思路跟解法～

題目

提示

你可能會用到的：

1. 高斯符號不等式：$x - 1 < \lfloor x \rfloor \leq x$。
2. 調和級數：$1 + 1/2 + 1/3 + \dots + 1/N \approx O(\log N)$
3. 數論分塊 :)

解法

這題是 Wiwi 放在讀書會拿來講解的題目，但我沒有聽不想被暴雷，結果想了超久才想到這題的作法 zzz。

強烈建議這題畫圖跟自己舉例。

看到 $2^{40}$ 又是數學題，明顯就是一題數論分塊題。

首先這題有個觀察，如果 $i$ 是邊緣人的話，那麼所有大於 $i$ 的 $j$ 也會是邊緣人。

接著計算答案的方式可以由 $x$ 的角度切入，枚舉 $x \in [1, N]$ 然後算每個 $x$ 會貢獻到 $[L, R]$ 當中的哪些人的答案（也就是會讓誰成為邊緣人）。但這樣複雜度會炸掉，所以我們考慮分塊。

對於 $\leq \lfloor \sqrt{N} \rfloor$ 的 $x$，可以直接枚舉每個這樣的 $x$ 然後簡單地計算。

設 $k = x \lfloor \frac{N}{x} \rfloor$，$x$ 會讓編號大於等於 $k+1$ 的人都成為邊緣人，但詢問只有問 $L \sim R$ 的人，所以只要把 $\max(k+1, L) \sim R$ 的人的答案全部 $+1$（當然，$k+1$ 如果 $> R$ 那就什麼事情都不用做）。

接下來處理 $> \lfloor \sqrt{N} \rfloor$ 的 $x$，這時候我們換另一個角度算答案，從原本枚舉一組的大小 $x$，換成枚舉組的數量 $t$，$t \in [1, O(\sqrt{N})]$。

當一共分成 $t$ 組時，考慮一組的大小 $x$ 的範圍，可以用高斯符號的不等式性質推出：

$$\begin{aligned} \frac{N}{x} - 1 &< \lfloor \frac{N}{x} \rfloor \leq \frac{N}{x} \\ \frac{N}{x} - 1 &< t \leq \frac{N}{x} \\ \frac{N}{t+1} &< x \leq \frac{N}{t} \\ x &\in [\lfloor \frac{N}{t+1} \rfloor + 1, \lfloor \frac{N}{t} \rfloor] \end{aligned}$$

姑且設 $x \in [l, r]$。

然後考慮這個區間每個 $x$ 會讓某個人成為邊緣人的「開始點」，會發現開始點就是 $tx + 1$，於是把 $\max(tx+1, L) \sim R$ 的人的答案 $+1$，於是對每個 $x \in [l, r]$ 做一樣的事情，起始點分別是 $tl+1, t(l+1)+1, t(l+2)+1, \dots, tr+1$ 然後做區間加值。

最後還有個優化，由於 $t$ 很小的時候，起始點的數量會太多，複雜度還是會炸掉。然而觀察發現這些起始點大部分都會小於 $L$，所以我們可以直接先快速算小於 $L$ 的起始點有幾個，一樣要推個不等式但這裡我就不細寫，總之可以 $O(1)$ 算出。然後對於 $[L, R]$ 內起始點我們便暴力掃過它們然後做區間加值。

注意到最後才要輸出答案，所以所有的加值過程可以直接用前綴和優化單次 $O(1)$ 加值，不需要線段樹，這樣均攤複雜度會是 $O((R-L)/1) + O((R-L)/2) + \dots + O((R-L)/\lfloor \sqrt{N} \rfloor) \in O((R-L)\log \sqrt{N})$。

於是總時間複雜度會是 $O(\sqrt{N} + (R-L)\log \sqrt{N})$。

以下是 init() 跟 solve() 函式的程式碼：

ll n, L, R;
ll ans[maxn];  // map [L, R] -> [0, R-L]

void init() {
    cin >> n >> L >> R;
}

void solve() {
    ll cut = 1;
    for (; cut*cut <= n; cut++) {
        ll p = max(cut*(n/cut)+1, L);
        if (p > R) continue;
        ans[p-L]++;
    }
    cut--;
 
    for (ll t = n/cut-1; t >= 1; t--) {
        ll x = n/(t+1)+1;
        ll p = t*x+1;
        if (p < L) {
            ll v = (L-p+t-1)/t;
            p += v*t;
            ans[0] += v;
        }
        for (; p <= R; p += t) ans[p-L]++;
    }
    
    FOR(i, 1, R-L+1, 1) ans[i] += ans[i-1];
    REP(i, R-L+1) cout << ans[i] << ' ';
    cout << endl;
}

我知道我這樣寫一定沒有人看得懂，但當你拿起筆開始算的時候就會知道我在說什麼了，總之這題很有趣，推大家寫 :D

兩年前有參加這場 NPSC，然後我記得那時候一直盯著這題卡很久，是完全沒有任何想法乾燒 5 小時，隔了一年終於把它解決掉了，現在想想那時候真的好笨，其實現在也是 =w=。