莫比乌斯反演
莫比乌斯反演是数论中的重要内容。对于一些函数，如果很难直接求出它的值，而容易求出其倍数和或约数和，那么可以通过莫比乌斯反演简化运算，求得这个函数的值。
开始学习莫比乌斯反演前，我们需要一些前置知识：积性函数、Dirichlet 卷积、莫比乌斯函数。
数论分块:
/problem/P2261
#include <cstdio>#include <algorithm>#include <iostream>using namespace std;typedef long long ll;int main() {ll n, k;cin >> n >> k;long long ans = n * k;for (ll i = 1, j; i <= n; i = j + 1) {if (k / i != 0){j = min(k / (k / i), n); }else{// break;j = n; // i大于k时}ans -= (k / i) * (j - i + 1) * (i + j) / 2; // 等差数列求和 }cout << ans << endl; return 0;}
莫比乌斯函数
线筛:
void get_mu(int n){mu[1]=1;for(int i=2;i<=n;i++){if(!vis[i]){prim[++cnt]=i;mu[i]=-1;}for(int j=1;j<=cnt&&prim[j]*i<=n;j++){vis[prim[j]*i]=1;if(i%prim[j]==0)break;else mu[i*prim[j]]=-mu[i];}}}
#include<cstdio>#include<cstdlib>#include<iostream>#include<algorithm>using namespace std;#define N 10000010#define debug cout<<__LINE__<<" "<<__FUNCTION__<<"\n"inline int read(){int x=0;char ch=getchar();while(ch<'0'||ch>'9'){ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x;}void put(long long x){if(x<0) putchar('-'),x=-x;if(x>=10) put(x/10);putchar((x%10)+48);}int prime[N>>2],n,m,cnt;bool ispri[N];int mu[N],num[N];inline void pri(){register int i,j;for(i=2;i<=N-10;i++){if(!ispri[i]){prime[++cnt]=i;mu[i]=-1;}for(j=1;j<=cnt&&(i*prime[j]<=N-10);j++){if(i*prime[j]<=N-10) ispri[i*prime[j]]=1;if(i%prime[j]==0){break;}else{mu[i*prime[j]]=-mu[i];}}}int res;for(i=1;i<=cnt;i++){res=1;for(j=prime[i];j<=N-10;j+=prime[i],res++){num[j]+=mu[res];}}for(i=2;i<=N-10;i++) num[i]+=num[i-1];}signed main(){//freopen(".in","r",stdin);//freopen(".out","w",stdout);mu[1]=1;pri();int T=read(),l,r;long long ans = 0;while(T--){n=read();m=read();ans=0;if(n>m) swap(n,m);for(l=1,r;l<=n;l=r+1){r=min(n/(n/l),m/(m/l));ans+=(long long)(num[r]-num[l-1])*(n/l)*(m/l);}put(ans);putchar('\n');}//fclose(stdin);//fclose(stdout);return 0;}
