1.數論分塊的含義
數論分塊算法，就是枚舉出使得取整函數發生變化的地方。
例如，對表達式 ? n i ? \lfloor \frac{n}{i} \rfloor ?in??使用數論分塊算法，就可以在 O ( n ) O(\sqrt n) O(n?)的時間復雜度下枚舉所有滿足 ? n i ? 1 ? + 1 = ? n i ? \lfloor \frac{n}{i-1}\rfloor+1 = \lfloor \frac{n}{i} \rfloor ?i?1n??+1=?in??的 i 。
2.算法模板
long long r;
for(int l = 1; l <= n; l = r + 1)
{r = k/(k/l)；/*your code*/
}
變量 l 就是取整函數發生變化的位置，即滿足 ? n l ? 1 ? + 1 = ? n l ? \lfloor \frac{n}{l-1}\rfloor+1 = \lfloor \frac{n}{l} \rfloor ?l?1n??+1=?ln??(l = 1除外）的位置，變量 r 就是滿足 ? n x ? = ? n l ? \lfloor \frac{n}{x}\rfloor = \lfloor \frac{n}{l} \rfloor ?xn??=?ln??的所有x 中最大的一個。
直觀上，該過程時間復雜度小于 O ( n ) O(n) O(n)，因為每次往后跳的長度大于1，
該算法的實際復雜度為 O ( n ) O(\sqrt n) O(n?)。
正確性證明和時間復雜度證明，詳見此處。寫題不需要證明。
3.算法的優化點
將所有 ? n i ? \lfloor \frac{n}{i} \rfloor ?in??結果一樣的 i 一并取出，使得時間復雜度降為 O ( n ) O(\sqrt n) O(n?)。
涉及取整的地方均可能用到此算法，包括但不限于，整除(練習題1）、最大公因數(練習題3)、最小公倍數(練習題2)、取模(本文例題）。
4.例題
P2261 [CQOI2007] 余數求和
題目描述
給出正整數 n n n 和 k k k，請計算
G ( n , k ) = ∑ i = 1 n k m o d i G(n, k) = \sum_{i = 1}^n k \bmod i G(n,k)=i=1∑n?kmodi
其中 k m o d i k\bmod i kmodi 表示 k k k 除以 i i i 的余數。
輸入格式
輸入只有一行兩個整數，分別表示 n n n 和 k k k。
輸出格式
輸出一行一個整數表示答案。
輸入輸出樣例 #1
輸入 #1
10 5
輸出 #1
29
說明/提示
樣例 1 解釋
G ( 10 , 5 ) = 0 + 1 + 2 + 1 + 0 + 5 + 5 + 5 + 5 + 5 = 29 G(10, 5)=0+1+2+1+0+5+5+5+5+5=29 G(10,5)=0+1+2+1+0+5+5+5+5+5=29。
數據規模與約定
- 對于 30 % 30\% 30% 的數據，保證 n , k ≤ 1 0 3 n , k \leq 10^3 n,k≤103。
- 對于 60 % 60\% 60% 的數據，保證 n , k ≤ 1 0 6 n, k \leq 10^6 n,k≤106。
- 對于 100 % 100\% 100% 的數據，保證 1 ≤ n , k ≤ 1 0 9 1 \leq n, k \leq 10^9 1≤n,k≤109。
解題思路
- a % b = a ? ? a b ? ? b a \% b =a- \left \lfloor \frac{a}{b} \right \rfloor *b a%b=a??ba???b
- 求和時，前半部分和后半部分，分開處理。
- 數列 a i = i ? ? x i ? a_i =i * \left \lfloor \frac{x}{i} \right \rfloor ai?=i??ix??，在 ? x i ? \left \lfloor \frac{x}{i} \right \rfloor ?ix??為不變值的時候，是等差數列。
AC代碼
#include<bits/stdc++.h>
#define int long longusing namespace std;
typedef pair<int,int> PII;
const int mod = 998244353;
void solve()
{int n,k;cin >> n >> k;long long ans = 0;ans += n*k;int r;for(int i = 1; i <= n; i = r + 1){if(k/i == 0) break;r = min(k/(k/i),n);ans -= (r-i+1)*(i+r)/2 *(k/i);}cout << ans << '\n';
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);int t = 1;//cin >> t;while(t --){solve();}
}
練習題
- 【AtCoder Regular Contest 150B】
- 【2025CCPC北京市賽】
- 【2021ICPC陜西省賽】
)
