TOI 初選倒數 15 天，今天戳了一題滿有趣的題目，想記錄一下這題的思路跟解法，順便讓自己不要一直頹下去還沒有自覺 =w=

札記

這幾個禮拜都嚴重睡眠不足，連 4 個睡眠週期都睡不到

結果今天直接睡到下午一點多，根本沒做什麼事 = =

寫了一點學校的功課然後只戳了一題，今天有點廢 =w=

2020 NPSC 初賽 pA — 邊緣人

題目

有 $N$ 個人（編號 $1 \sim N$）要分組，由 $1$ 號開始每 $x$ 人分成一組，最後沒有組的 $N\mod x$ 個人就是邊緣人。

定義函數 $f(i)$ 為編號 $i$ 的人在 $x = 1, 2, …, N$ 的情況中，是邊緣人的情況總數。

給定 $N, L, R$，輸出 $f(L), f(L+1), …, f( R )$。

$1 \leq N \leq 2^{40}$

$L \leq R \leq N$

$R - L \leq 3 \times 10^5$

提示

你可能會用到的：

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

解法

這題是 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$ 的範圍，可以用高斯符號的不等式性質推出：

$$\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]$$

姑且設 $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, … tr+1$ 然後做區間加值。

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

注意到最後才要輸出答案，所以所有的加值過程可以直接用前綴和優化單次 $O(1)$ 加值，不需要線段樹，這樣均攤複雜度會是 $O((R-L)/1) + O((R-L)/2) + … + 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=。

結語

最近心情其實滿焦慮的，要做事情真的比我想像的多，一直擔心做不完然後又沒力氣開始做事，差一點又快撐不住崩潰zzz

幸好晚上有找朋友聊天，聊了滿久的，聊完以後心情意外好很多，也覺得有動力繼續向前了！