JZTXT

整除分块

发布时间 2023-10-12 15:52:28作者: yzq_yzq

证明

数论分块板子求 $ \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. 减法。选择一个 $ [1, x - 1] $ 中的正整数 $ y $，将点移动到 $ x - y $ 号格子中。

  2. 除法。选择一个 $ [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$$