证明
数论分块板子求 $ \large \sum_{i=1}^n [n/i]$ ,其中 $n \leq 10^{10}$
很明显，暴力求的复杂度是 $O(n)$ 的，需要优化
其中，例 $n=10$ 时，$[10/4]=[10/5]$ 是有相等的值的
不妨设第一个 $[n/i]=x$ 的数为 $l$
则最后一个有 $[n/i]=x$ 的数 $\large r= [\frac{n}{[n/l]}]$
理由如下：
不妨设 $n=p \times [n/l] + q$ 其中 $p,q$ 为整数，$0 \leq q <[n/l]$
由 $\large r= [\frac{n}{[n/l]}]$ 得 $ r \times [n/l] \geq n$ , $r\times [n/l]+1>n$
所以 $[n/(r+1)]<[n/l]$ , $r$ 为最后一个 $[n/i]=x$ 的数
接下来说明 $[n/l]$ 最多只有 $2\times \sqrt n -1$
当 $1 \leq l \leq \sqrt n$ 时, 一共只有 $\sqrt n$ 个 $l$ ，所以最多只有 $\sqrt n$ 个 $[n/l]$
当 $\sqrt n < l \leq n$ 时，则用 $n$ 同时除去不等式两边 ，有 $\sqrt n > [n/l] \geq 1$ ， 最多有 $\sqrt n -1$ 个不同的 $[n/l]$
所以最多有 $2\times \sqrt n -1$ 个不同的 $[n/l]$
ll solve(ll n){
ll l = 1,r = 0,ans = 0;
for(;l <= n;l = r + 1) {
r = n / (n / l);
ans += (n / l) * (r - l + 1);
}
return ans;
}
例题
约数和 P2424
求 x 到 y 每个数所有约数的和
显然 $f(n)=\sum_{i=1}^n i \times [n/i]$ ，其中 $f(n)$ 代表 1 到 n 的约数和
对于每个块，$\sum_{i=l}^r i*[n/l]$ 用等差数列求和即可
$(=(r-l+1)\times(l+r) / 2\times [n/l])$
__int128 solve(__int128 n){
__int128 l = 1, r = 0, ans = 0;
for(;l <= n;l = r + 1){
r = min(n / (n / l), n);
ans += (n / l) * (l + r) * (r - l + 1) / 2;
}
return ans;
}
余数求和
求
$$G(n,k)= ∑_{i=1}^n k \mod i$$
$$
\begin{aligned}
ans &= ∑_{i=1}^n k \mod i\
&= ∑_{i=1}^n (n-[n/i]\times i) \
&=n \times k - ∑_{i=1}^n [n/i] \times i\
\end{aligned}
$$
ll solve(){
ll l = 1, r = 0, ans = n * m;
for(;l <= n;l = r + 1){
if(m / l == 0) break;
r = min(m / (m / l), n);
ans -= (m / l) * (l + r) * (r - l + 1) / 2;
}
return ans;
}
Sum of Remainders CF616E
求
$$\sum_{i=1}^m (n \mod i)$$
差不了多少
$$
\begin{aligned}
\sum_{i=1}^m (n \mod i) &= \sum_{i=1}^m(n-[n/i]*i) \
&=m\times n - \sum_{i=1}^{\min(n,m)} [n/i] \times i \
\end{aligned}
$$
__int128 solve(__int128 n) {
__int128 l = 1, r = 0, ans = n * m % mod;
m = min(m, n);
for (; l <= m; l = r + 1) {
if (n / l == 0)
break;
r = min(n / (n / l), m);
ans -= (l + r) * (r - l + 1) / 2 % mod * (n / l) % mod;
ans = (ans + mod) % mod;
}
return ans;
}
整除分块优化DP
Up the Strip CF1558B
题面描述
你有一张 $ 1 \times n $ 的纸带，由 $ n $ 个格子组成。初始有一个点在 $ n $ 号格子（即左数第 $ n $ 个）中。
假设现在这个点在 $ x\ (x > 1) $ 号格子，每次你可以对这个点进行如下操作中的一种：
-
减法。选择一个 $ [1, x - 1] $ 中的正整数 $ y $，将点移动到 $ x - y $ 号格子中。
-
除法。选择一个 $ [2, x] $ 中的正整数 $ z $，将点移动到 $ \lfloor \frac{x}{z} \rfloor $ 号格子中。
当点在 $ 1 $ 号格子中时无法移动，操作结束。
求将点从 $ n $ 号格子移到 $ 1 $ 号格子的方案数，答案对给定的模数取模。
易得转移方程
$$f[x]=\sum_{i=1}^{x-1}f[i] + \sum_{i=2}^{x} f[[n/i]]$$
第一部分用前缀和维护，第二个部分可以用整除分块求解。
ll solve(ll n) {
ll l = 2, r = 0, ans = 0;
for (; l <= n; l = r + 1) {
r = n / (n / l);
ans += (r - l + 1) * f[n / l] % mod;
ans %= mod;
}
return ans;
}
for (ll i = 2; i <= n; i++) {
f[i] = (sum[i - 1] + solve(i)) % mod;
sum[i] = sum[i - 1] + f[i];
}
较难的问题
gcd HDU5780
求
$$∑gcd({x}{a}-1,{x}-1) (1\leq a,b\leq n)$$
不妨设 $b>a$ ，则
$$
\begin{aligned}
gcd(xa-1,xb-1)&=gcd(xa-1,xb-1-x{b-a}(xa-1))\
&=gcd(xa-1,xb-1-xb+x)\
&=gcd(xa-1,x-1) \
&=x^{gcd(a,b)}-1
\end{aligned}
$$
很容易想到枚举 $gcd(a,b)$ 的做法：
确定 $gcd(a,b)$ ，然后枚举 $a$ ，则 $b$ 的情况数就等于 $phi[a/gcd(a,b)]$ （$gcd(\frac{a}{gcd(a,b)},\frac{b}{gcd(a,b)})=1$）
答案就等于
$$ \sum_{i=1}^n (\sum_{j=1}^{j*i\leq n}( phi[j] \times 2-1) -1)\times (x^i-1)$$
ll f(ll a, ll b) {
if (a == 1)
return b;
if (a == 0)
return 1;
ll w = f(a / 2, b);
if (a % 2)
return w * w % mod * b % mod;
return w * w % mod;
}
ll solve(ll x, ll n) {
ll ans = 0, sum = 0;
for (ll i = 1; i <= n; i++) {
ll w = f(i, x);
ans -= w - 1;
ans = (ans + mod) % mod;
for (ll j = i; j <= n; j += i) {
sum += phi[j / i];
ans += (w - 1) * phi[j / i] * 2 % mod;
ans %= mod;
}
}
return ans;
}
但是会 $TLE$
我们可以想到 $phi[j/i]$ 是一段连续的 $phi[1]$ 到 $phi[n/i]$
所以可以把 $phi$ 前缀和变成 $phif$ 数组
ll solve(ll x, ll n) {
ll ans = 0, sum = 0;
ll w = 1;
for (ll i = 1; i <= n; i++) {
w = w * x % mod;
ans -= w - 1;
ans = (ans + mod) % mod;
ll cnt = (w - 1) * phif[n / i] % mod * 2 % mod;
ans += cnt;
ans %= mod;
}
return ans;
}
结果又 $TLE$ 了
但现在的问题也可以转化为求
$$\sum_{i=1}^n (x^i -1) \times(phif[n/i]*2-1)$$
这个可以拆开，就变成了
$$\sum_{i=1}^n x^i \times(phif[n/i]2-1) -\sum_{i=1}^n (phif[n/i]2-1)$$
前面一部分用数论分块的时候，每一块里的和等于
$$\sum_{i=l}^r x^i \times phif[n/l]$$
用等比数列求和可得等于
$$ x^l \times \frac{x^{r-l+1}-1}{x-1} \times phif[n/l]$$
就可以用整除分块啦
ll f(ll a, ll b) {
if (a == 1)
return b % mod;
if (a == 0)
return 1;
ll w = f(a / 2, b);
if (a % 2)
return w * w % mod * b % mod;
return w * w % mod;
}
ll solve(ll x, ll n) {
ll ans = 0;
ll w = x;
ll l = 1, r = 0, inv = f(mod - 2, x - 1);
for (; l <= n; l = r + 1) {
r = n / (n / l);
ans -= (r - l + 1) * (phif[n / l] * 2 - 1) % mod;
ans = (ans + mod) % mod;
}
l = 1;
for (; l <= n; l = r + 1) {
r = n / (n / l);
ll o = f(r - l + 1, x);
ans += w * (o % mod - 1) % mod * inv % mod * (phif[n / l] * 2 - 1) % mod;
ans %= mod;
w = w * o % mod % mod;
}
return ans;
}
整除分块+矩阵加速
Sequence HDU6395
求 $F_n$ ，其中
$$
\left{\begin{aligned}
F_1 &= A \
F_2 &= B \
F_n &=C\cdot{}F_{n-2}+D\cdot{}F_{n-1}+\left\lfloor\frac{P}{n}\right\rfloor
\end{aligned}\right.
$$
$[\frac{P}{n}]$ 一定时，易得
$$
\begin{pmatrix}
F_{n-2} & F_{n-1} &[\frac{P}{n}] \
0 & 0 & 0 \
0 & 0 & 0
\end{pmatrix}
\times
\begin{pmatrix}
0 & C & 0 \
1 & D & 0 \
0 & 1 & 1
\end{pmatrix}
$$
如果 $ \lfloor \frac{P}{n} \rfloor$ 是个定值就很容易用矩阵加速解决，所以我们可以用整除分块求出每个不同的 $ \lfloor \frac{P}{n} \rfloor$ ，再做矩阵加速即可
inline void init() {
basic.a[1][1] = 0, basic.a[1][2] = c, basic.a[1][3] = 0;
basic.a[2][1] = 1, basic.a[2][2] = d, basic.a[2][3] = 0;
basic.a[3][1] = 0, basic.a[3][2] = 1, basic.a[3][3] = 1;
}
inline void ans_init() {
ans.a[1][1] = a, ans.a[1][2] = b, ans.a[1][3] = P / 3;
ans.a[2][1] = 0, ans.a[2][2] = 0, ans.a[2][3] = 0;
ans.a[3][1] = 0, ans.a[3][2] = 0, ans.a[3][3] = 0;
}
void sum(ll KK, ll n) {
ans.a[1][3] = KK;
init();
while (n) {
if (n & 1)
ans = ans * basic;
basic = basic * basic;
n >>= 1;
}
}
ll solve() {
ll l = 3, r = 0;
for (; l <= n; l = r + 1) {
if (P / l != 0)
r = min(P / (P / l), n);
else
r = n;
sum(P / l, r - l + 1);
}
return ans.a[1][2];
}
$$\Huge End$$
标签：分块,sum,basic,times,ans,整除,ll,mod From： https://www.cnblogs.com/yzq-yzq/p/17759683.html