BZOJ 3994 - [SDOI2015]约数个数和

#数学 #莫比乌斯反演 #线性筛
Published on 2016-08-13

题目地址

描述

设 d(x)d(x) 为 xx 的约数个数，有 T(T≤50000)T(T\le 50000) 组询问，每次给定 n,m(n,m≤50000)n, m(n, m\le 50000)，求：

∑i=1n∑j=1md(i⋅j)\sum_{i = 1}^n\sum_{j = 1}^md(i\cdot j)

分析

首先有一个结论：

d(nm)=∑i∣n∑j∣m[gcd(i,j)=1]d(nm) = \sum_{i\mid n}\sum_{j\mid m}[\gcd(i, j) = 1]

证明：设 nm=p1x1⋅p2x2⋅p3x3⋯pkxknm = p_1^{x_1}\cdot p_2^{x_2}\cdot p_3^{x_3}\cdots p_k^{x_k}，且 n=p1y1⋅p2y2⋅p3y3⋯pkykn = p_1^{y_1}\cdot p_2^{y_2}\cdot p_3^{y_3}\cdots p_k^{y_k}，则 m=p1x1−y1⋅p2x2−y2⋅p3x3−y3⋯pkxk−ykm = p_1^{x_1 - y_1}\cdot p_2^{x_2 - y_2}\cdot p_3^{x_3 - y_3}\cdots p_k^{x_k - y_k}。
设 i=p1a1⋅p2a2⋅p3a3⋯pkaki = p_1^{a_1}\cdot p_2^{a_2}\cdot p_3^{a_3}\cdots p_k^{a_k}，j=p1b1⋅p2b2⋅p3b3⋯pkbkj = p_1^{b_1}\cdot p_2^{b_2}\cdot p_3^{b_3}\cdots p_k^{b_k}，要使 gcd(i,j)=1\gcd(i, j) = 1，必然有 a1a_1 或 b1b_1 为 0，如果 a1a_1 为 0，那么 b1b_1 有 xi−y1+1x_i - y_1 + 1 种取值；如果 b1b_1 为 0，那么 a1a_1 有 y1+1y_1 + 1 种取值，一共有 x1+1x_1 + 1 种取值，对于 xix_i 也如此。
所以满足条件的 i,ji, j 对数为 ∏(xi+1)\prod(x_i + 1)，与约数定理给出的形式一样，得证。

回到原式，我们化简一下，其中第二个等号用到了莫比乌斯函数的一个性质：

∑x∣nμ(x)=[n=1]\sum_{x\mid n}\mu(x) = [n = 1]

由于 d(n)d(n) 是积性函数，所以可以 O(n)O(n) 线筛预处理，至此式子转换为可以分块的形式，单组询问可以在：O(n)O(\sqrt n) 的时间内解决。

复杂度：O(n+Tn)O(n + T\sqrt n)。
本题技巧性比较强，变换比较多，需要熟练掌握莫比乌斯的分块处理技巧，有什么问题可以直接留言。

代码

//  Created by Sengxian on 8/13/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 3994 莫比乌斯反演 + 线性筛
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int maxn = 50000 + 3;
int primes[maxn], num;
int mu[maxn], sigma[maxn], sumMu[maxn];
ll sumSigma[maxn];
bool isPrime[maxn];

void sieve() {
    static int minPrimeCnt[maxn];
    fill(isPrime, isPrime + maxn, 1);
    mu[1] = 1, sigma[1] = 1, num = 0;
    for (int i = 2; i < maxn; ++i) {
        if (isPrime[i]) primes[num++] = i, mu[i] = -1, sigma[i] = 2, minPrimeCnt[i] = 1;
        static int d;
        for (int j = 0; j < num && (d = i * primes[j]) < maxn; ++j) {
            isPrime[d] = false;
            if (i % primes[j] == 0) {
                mu[d] = 0;
                minPrimeCnt[d] = minPrimeCnt[i] + 1;
                sigma[d] = sigma[i] / (minPrimeCnt[i] + 1) * (minPrimeCnt[d] + 1);
                break;
            } else mu[d] = -mu[i], sigma[d] = sigma[i] << 1, minPrimeCnt[d] = 1;
        }
    }
    sumMu[0] = 0;
    for (int i = 1; i < maxn; ++i) sumMu[i] += sumMu[i - 1] + mu[i];
    for (int i = 1; i < maxn; ++i) sumSigma[i] += sumSigma[i - 1] + sigma[i];

}

inline ll F(int n, int m) {
    if (n > m) swap(n, m);
    ll ans = 0;
    for (int i = 1, j = 1; i <= n; i = j + 1) {
        j = min(n / (n / i), m / (m / i));
        ans += (sumMu[j] - sumMu[i - 1]) * sumSigma[n / i] * sumSigma[m / i];
    }
    return ans;
}

int main() {
    sieve();
    int caseNum = ReadInt();
    while (caseNum--) {
        int n = ReadInt(), m = ReadInt();
        printf("%lld\n", F(n, m));
    }
    return 0;
}
BZOJ 3930 - [CQOI2015]选数