新專輯

https://tioj.ck.tp.edu.tw/problems/1674

Description

最近你打算訂購$N^2$張水樹奈奈的專輯《極限魅惑IMPACT EXCITER》。
由於份量實在是太多了，你決定分散成$N$份訂單。

然而，不幸的，依據博客來新的訂貨規定，每一位顧客第$k$次下訂單所訂的CD張數必頇是$k$的正整數倍。
換句話說，一位顧客第$5$次訂的CD張數只可能是$5$張、$10$張、$15$張、…依此類推。

當然，原先你把$N^2$張CD分散在$N$份訂單的目的就是為了讓一張訂單中最多只會有$N$張CD。
即使博客來多了這項奇怪的規定，你仍然不打算捨棄你的原則，只是這樣每份訂單訂的數量可能會達不到你原來的期望。

無論如何，你還是下了訂單。為了估計你實際訂下的CD數與你期望訂下的CD數的差別，你決定把每次你少訂的數量加起來。
可是，因為你可能少訂非常多張CD，所以你希望算出少訂的總數量除以$10^9+9$的餘數。

也就是說，如果你總共要訂$3^2$張CD，分成三次訂的話，
那你第一、第二、第三次分別可以訂$3$、$2$、$3$張CD，分別會少訂是$0＋1＋0＝1$張CD。

Solution

仔細讀懂題目之後可以發現題目要求的就是

$$
\sum _ {i=1}^n n\%i
$$

不過$n$可以到$10^{13}$不能直接$\mathcal{O}(n)$跑過去

數論分塊

數論分塊的精神很簡單，不同的$\lfloor n/i \rfloor$數量只有$\mathcal{O}(\sqrt{n})$種

說明:
對於$i \leq \sqrt{n}$，最多只有$\sqrt{n}$種不同的值
對於$i > \sqrt{n}$，$\lfloor n/i \rfloor < \sqrt{n}$最多也只有$\sqrt{n}$種不同的值

怎麼快速枚舉可能的$\lfloor n/i \rfloor$？

1
2
3
4
5
6

for(int i = 1,j,x; i <= n; i = j+1) {
	x = n/i;
	j = n/x;
	// j是最大的數字使得j*x <= n，意即[i,j]區間內正好是所有n/k=x的數字
	// use n/i here
}

回到剛剛的式子，把他改寫成

$$
\sum _ {i=1}^n n - i \cdot \lfloor \frac{n}{i} \rfloor
$$

後面那項等價於算區間$\sum _ {k=i}^j k \cdot x$
其中區間$[i,j]$是所有$\lfloor n/k \rfloor = x = \lfloor n/i \rfloor$的$k$
小學數學算一算就可以知道這是$x \cdot (\frac{j(j+1)}{2} - \frac{(i-1)i}{2})$的啦

記得小心處理模$10^9+9$的部分，尤其因為$n$可以到$10^{13}$，兩個數字乘起來的時候都要先模一次

AC code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <iostream>
using namespace std;
typedef long long ll;
const ll MOD = 1000000009;

ll modpow(ll e, ll p) {
    ll r = 1;
    while(p) (p&1)&&(r=r*e%MOD), e=e*e%MOD, p>>=1;
    return r;
}
signed main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    ll n,sum = 0;
    cin >> n;
    for(ll i = 1,j; i <= n; i = j+1) {
        j = n/(n/i);
        ll x = (n/i)%MOD;
        ll sr = (j%MOD)*((j+1)%MOD)%MOD;
        ll sl = (i%MOD)*((i-1)%MOD)%MOD;
        sum = (sum + x * (sr - sl + MOD))%MOD;
    }
    ll s = (n%MOD)*(n%MOD)%MOD;
    cout << (s - sum * modpow(2, MOD-2) % MOD + MOD) % MOD << '\n';
}