BZOJ3309 DZY Loves Math <莫比乌斯反演>

Problem

DZY Loves Math

Description

对于正整数，定义为所含质因子的最大幂指数。例如, , 。
给定正整数，求。

Input

第一行一个数，表示询问数。
接下来行，每行两个数，表示一个询问。

Output

对于每一个询问，输出一行一个非负整数作为回答。

Sample Input

4
7558588 9653114
6514903 4451211
7425644 1189442
6335198 4957

Sample Output

35793453939901
14225956593420
4332838845846
15400094813

HINT

标签：莫比乌斯反演

Solution

好题，线筛新姿势。

首先套路转化出莫比乌斯函数：

这时会发现前面用根号分块很好处理，而后面的部分需要计算，所以需要线性筛预处理。

令，考虑通过与的性质找到其积性关系。

设，，
那么一定有，否则，不计入总贡献。

若
- 对于的情况，只有一种，即。而。故贡献为；
- 对于的情况，根据组合原理，有，而又由二项式基本定理知，因而贡献为。
- 故此情况。
若使得
- 不论还是，都存在至少一个质因数使得不论取还是对的取值都没有影响。然而取或会使得取到或，此处的贡献为，一定全部被抵消。
- 故此情况。

综上，线性筛预处理需要知道每个数最小的质因数的次数和最小质因数的幂指数次幂，这样看是否有即可知的最小与次小质因数的次数是否相等，由此可判断是情况还是情况。这样先线性筛预处理后，对每次询问进行根号分块，即可达到的复杂度。

Code

#include <bits/stdc++.h>
#define MAX_N 10000000
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int g[MAX_N+5], sp[MAX_N+5], num[MAX_N+5];
int pri[MAX_N+5], cnt;	lnt ans;
bool NotPri[MAX_N+5];
void init(int n) {
    NotPri[0] = NotPri[1] = true;
    for (int i = 2; i <= n; i++) {
        if (!NotPri[i]) pri[cnt++] = sp[i] = i, g[i] = num[i] = 1;
        for (int j = 0; j < cnt; j++) {
            if (i*pri[j] > n) break;	NotPri[i*pri[j]] = true;
            if (i%pri[j]) sp[i*pri[j]] = pri[j], num[i*pri[j]] = 1, g[i*pri[j]] = num[i] == 1 ? -g[i] : 0;
            else sp[i*pri[j]] = sp[i]*pri[j], num[i*pri[j]] = num[i]+1, 
                g[i*pri[j]] = sp[i] == i ? 1 : (num[i/sp[i]] == num[i*pri[j]] ? -g[i/sp[i]] : 0);
            if (i%pri[j] == 0) break;
        }
    }
    for (int i = 1; i <= n; i++) g[i] += g[i-1];
}
int main() {
    int T;	read(T), init(MAX_N);
    while (T--) {
        int a, b;	read(a), read(b), ans = 0;
        for (int l = 1, r; l <= min(a,b); l = r+1)
            r = min(a/(a/l), b/(b/l)), ans += 1LL*(a/l)*(b/l)*(g[r]-g[l-1]);
        printf("%lld\n", ans);
    }
    return 0;
}