BZOJ2671 Calc <莫比乌斯反演>

Problem

Calc

Description

给出，统计满足下面条件的数对的个数：

Input

一行一个数。

Output

一行一个数表示答案。

Sample Input

Sample Output

HINT

测试点编号	数据规模	测试点编号	数据规模

标签：莫比乌斯反演

Solution

一道稍有变形的莫比乌斯反演，有的算法，但我只会小常数的算法，不过可以过数据。

问题即求的值。设, , ，易知。
那么。
不妨设，那么, 。
有

显然只有级别种取值，可以根号分块来算，即枚举，每次找到相等的一段，统计间满足的的个数，可以套用基础莫比乌斯反演公式，即。

此算法先枚举的取值，再枚举的取值，最后枚举的约数计算反演。其中有级别种取值，所对应的都在之间，即共有级别种取值，而最后的又有级别种取值，故总时间复杂度应为。但是由于的取值总数通常到不了级别，且的取值总数通常也到不了级别，因此常数非常小，跑得贼快，可以过此题级别的数据。

Code

#include <bits/stdc++.h>
#define MAX_N 100000
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 pri[MAX_N+5], mu[MAX_N+5], fac[MAX_N+5], cnt;	bool NotPri[MAX_N+5];
void PriS() {
    mu[1] = 1;
    for (int i = 2; i <= MAX_N; i++) {
        if (!NotPri[i]) pri[cnt++] = i, mu[i] = -1;
        for (int j = 0, x; j < cnt; j++) {
            if ((x = i*pri[j]) > MAX_N) break;
            NotPri[x] = true;
            if (i%pri[j]) mu[x] = -mu[i];
            else {mu[x] = 0;	break;}
        }
    }
}
int main() {
    int n;	read(n), PriS();	lnt ans = 0LL;
    for (lnt i = 1, l, r; i < sqrt(n); i++) {
        cnt = 0; for (int j = 1; j <= sqrt(i); j++) if (i%j == 0) fac[cnt++] = j;
        for (l = 1; l < i; l = r+1) {
            lnt val = n/(i*(i+l)); if (!val) break;	r = min(n/val/i-i, i-1);
            for (lnt k = 0, j; k < cnt; k++) {
                j = fac[k], ans += mu[j]*(r/j-(l-1)/j)*val;	lnt t = i/j;
                if (i%t == 0 && (j^t)) ans += mu[t]*(r/t-(l-1)/t)*val;
            }
        }
    }
    return printf("%lld\n", ans), 0;
}