当前位置：首页 > news >正文

整除分块

news 来源：原创 2024/5/9 9:27:22

问题引入

求 $\sum_{i=1}^k⌊\frac{n}{i}⌋,n \leq 10^{14}$

等价定义

设 $d (x)$ 为 $x$ 的因子个数，则上述问题等价于 $\sum_{i=1}^kd(i)$

又根据因数个数定理，设 $x$ 的质因数分解式为 $x=P_1^{a_1} *P_2^{a_2}*...*P_n^{a_n}$ ，令 $g(x)=(a_1+1)*(a_2+1)...(a_n+1)$ ，那么也等价于 $\sum_{i=1}^kg(i)$

若范围较小， $\sum_{i=1}^td(i)$ 可以线性筛预处理，原理是： $d (i)$ 是积性函数

欧拉筛时每个数只由它最小的质因子筛出，那么我们使用数组 $a$ 记录每个数最小质因子的幂次， $d$ 记录每个数的因子个数。当遇到质数时，显然 $a [i] = 1, d [i] = 2$ ；当 $i\%p!=0$ 时，证明 $i * p$ 的最小质因子为 $p$ 且 $i\bot p$ ，而 $i$ 的因子个数已经求出，那么 $d [i * p] = d [i] * 2, a [i] = 1$ ；当 $i\%p==0$ 时，显然我们只需要修改答案中 $p$ 的乘积因子，即由原来的 $\rightarrow a[i]+2$ ， $a [i * p] = a [i] + 1$

代码

ll d[maxn];
vector<int> prime;
bitset<maxn> vis;

void init() {
    d[1] = 1;
    for (int i = 2; i < maxn; i++) {
        if (!vis[i]) {
            prime.push_back(i);
            d[i] = 2, a[i] = 1;
        }
        for (int j = 0; j < prime.size() && i * prime[j] < maxn; j++) {
            vis[i * prime[j]] = 1;
            if (i % prime[j]) {
                d[i * prime[j]] = d[i] * 2;
                a[i * prime[j]] = 1;
            } else {
                d[i * prime[j]] = d[i] / (a[i] + 1) * (a[i] + 2);
                a[i * prime[j]] = a[i] + 1;
                break;
            }
        }
        d[i] += d[i - 1];
    }
}

分析

显然枚举会超时，因为有很多 $⌊\frac{n}{i}⌋$ 是一样的，那么需要分块计算，即将相等的一部分一次求出。而且打表可以发现都是相同的 $⌊\frac{n}{i}⌋$ 会连续出现

设 $⌊\frac{n}{j}⌋$ 和 $⌊\frac{n}{i}⌋$ 相等，则 $j$ 的最大值为 $⌊\frac{n}{⌊\frac{n}{i}⌋}⌋$ 。根据这个结论，只需要设置两个变量 $l, r$ ，每次令 $r=⌊\frac{n}{⌊\frac{n}{l}⌋}⌋$ ，一次计算出相同部分

因为 $n$ 以内的因数最多有 $2\sqrt{n}$ 种，那么时间复杂度为 $O(\sqrt{n})$

代码

ll cal(ll n, ll k) {
    ll ans = 0;
    for (ll l = 1, r; l <= k; l = r + 1) {
        r = n / (n / l);
        if (r > k) r = k;
        ans += (n / l) * (r - l + 1);
    }
    return ans;
}

二维整除分块

求 $\sum_{i=1}^{min(n,m)} \lfloor \frac{n}{i} \rfloor \lfloor \frac{m}{i} \rfloor$

ll cal(ll n, ll m) {
    ll ans = 0;
    ll up = min(n, m);
    for (ll l = 1, r; l <= up; l = r + 1) {
        r = min(n / (n / l), m / (m / l));
        if (r > up) r = up;
        //...
    }
    return ans;
}