莫比乌斯反演本质上就是一个容斥原理的应用。。。。
如果我们要求f(x) 直接求不好求但是F（x)=f(x1)+f(x2)+..........(x1,x2,x3...xn整除x)如果F(x)好求的话我们就阔以先求出F(x)再反演求f(x).
然后还有一个重要的地方就是你反演后还是有一大堆式子，但是注意到[x]当 m-1<x<=m的时候[x]=m这个性质，就阔以提共因式，剩下的就是求一堆前缀和了。so,easy!!!
下面的资料讲的很详细。
嗯，这个东西我从大一开始看数论，现在已经快大三了然后搞懂了。。智商捉急233333331109484307
主要看3本书就够了《初等数论》二潘的嗯，这本书我看了快两年了。。。断断续续看下。。。不得不说数论还是有那么难的。。。。。
《组合数学》第五版，以前版本没莫比乌斯反演。。《具体数学》嗯，讲的很不错，三本书各有优点都看下。。
然后就是这个https://wenku.baidu.com/view/ff2f649b852458fb760b56d4.html?re=view良心之作，比网上的大多数教程都好的多！！！！！！！！
然后再看下贾志鹏的线性筛那篇论文。。。差不多就这些。。。
本来说自己讲讲的，但是我水平太差啦啦。。。真的是很感谢写那些教程的大佬们。。人类之所以这么聪明，交流应该是主要作用！！！！！！
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; typedef long long ll; int n, m; ll sum[10000500]; int u[10000500]; int ischeck[10000500]; int prime[8000000]; int cnt; long long ans; void mobi_wizard() { sum[1] = 0; sum[0] = 0; for (int i = 2; i <= 10000000; i++) { if (!ischeck[i]) { ischeck[i] = 1; sum[i] = 1; u[i] = -1; prime[cnt++] = i; } for (int j = 0; i*prime[j] <= 10000000; j++) { ischeck[i*prime[j]] = 1; if (i%prime[j]==0) { sum[i*prime[j]] = u[i]; u[i*prime[j]] = 0; break; } sum[i*prime[j]] = u[i] - sum[i]; u[i*prime[j]] = -u[i];//注意莫比乌斯函数是积性函数但不是完全积性的。 } } for (int i = 2; i <= 10000000; i++) { sum[i] = sum[i] + sum[i - 1]; } } int main() { int t; mobi_wizard(); scanf("%d", &t); //cout << t << endl; while (t--) { scanf("%d%d", &n, &m); //cout << n << m << endl; ans = 0; if (n > m)swap(n, m); int last = 1000000000; for (int i = 2; i <= n; i = last + 1) { last = min(m /( m / i), n / (n / i)); ans += (sum[last] - sum[i - 1])*(m / i)*(n / i); } printf("%lld\n", ans); } }
