莫比乌斯反演 (Möbius Inversion)
[ 莫比乌斯反演公式 ]
设 ,
为定义于正整数域上的两个函数,并满足:
则有以下反演公式:
[ 莫比乌斯函数
]
[ 莫比乌斯反演相关推论 ]
为积性函数。
- 若数论和函数
为积性函数,则
为积性函数。
[ 莫比乌斯反演证明 ]
由推论 3 得:
显然又有:
将 代入
得:
由于 和
的限制条件等价于
,可得:
[ 莫比乌斯反演应用 ]
BZOJ 2301: https://www.lydsy.com/JudgeOnline/problem.php?id=2301
给出 组询问
,
,
,
,
,求
。
,
,
,
,
。
考虑计算出二维前缀和 ,则
答案即为 。
当 ,
时,令
表示
时
的对数,
表示
时
的对数,则
根据莫比乌斯反演公式,上式可化为
取 ,有
考虑计算 。
首先对 的取值进行讨论:
- 当
时,显然
最多有
种不同取值。
- 当
时,由于
,最多也有
种不同取值。
综上, 最多有
种不同取值,且相同取值一定连续。
当循环到 时,我们需要计算以
开始,
和
均不变的最大结束位置
:
- 计算以
开始,
不变的最大位置
。由于
必定是满足
的最大值,
。
- 计算以
开始,
不变的最大位置
。同理
。
。
根据上述分析,单次询问复杂度为 ,可以通过此题。
#include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<algorithm> using namespace std; typedef long long ll; inline void getint(int &num){ register int ch, neg = 0; while(!isdigit(ch = getchar())) if(ch == '-') neg = 1; num = ch & 15; while(isdigit(ch = getchar())) num = num * 10 + (ch & 15); if(neg) num = -num; } int T, A, B, C, D, K; int mu[50005], M[50005], prm[6005], pcnt = 0; bool notprm[50005]; inline void Euler_Sieve(int n){ notprm[1] = 1, mu[1] = 1; for(register int i = 2; i <= n; i++){ if(!notprm[i]) prm[++pcnt] = i, mu[i] = -1; for(register int j = 1; j <= pcnt && i * prm[j] <= n; j++){ notprm[i * prm[j]] = 1; if(i % prm[j] == 0) {mu[i * prm[j]] = 0; break;} mu[i * prm[j]] = -mu[i]; } } } inline ll calc(int n, int m){ ll res = 0; if(n > m) swap(n, m); for(register int i = 1, pos = 0; i <= n; i = pos + 1){ pos = min(n / (n / i), m / (m / i)); res += ll(M[pos] - M[i - 1]) * (n / i) * (m / i); } return res; } int main(){ Euler_Sieve(50000); for(register int i = 1; i <= 50000; i++) M[i] = M[i - 1] + mu[i]; getint(T); while(T--){ getint(A), getint(B), getint(C), getint(D), getint(K); A = (A - 1) / K, B /= K, C = (C - 1) / K, D /= K; printf("%lld\n", calc(B, D) - calc(A, D) - calc(B, C) + calc(A, C)); } return 0; }
Greggzon
Спасибо
Vickie
I do consider all the ideas you've offered for your post.
They are very convincing and will definitely work. Nonetheless, the posts are very quick for novices.
May just you please extend them a little from subsequent time?
Thanks for the post.