bzoj 2820 莫比乌斯反演

本文主要是介绍bzoj 2820 莫比乌斯反演，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

搞了一整个晚自习，只是看懂了dalao们的博客，目前感觉没有思路….还是要多切题
next day：
刚才又推了一遍，发现顺过来了，hahaha

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
const int N=10000000;
long long ans,f[N+5];
int mm[N+5],prime[N];
bool bo[N];
int T,n,m,tot;
void init(){mm[1]=1;for(int i=2;i<=N;i++){if(!bo[i]){prime[++tot]=i;mm[i]=-1;}for(int j=1;j<=tot&&i*prime[j]<=N;j++){bo[i*prime[j]]=1;if(i%prime[j]!=0)mm[i*prime[j]]=-mm[i];else{mm[i*prime[j]]=0;break;}}}for(int j=1;j<=tot;j++)for(int i=1;i*prime[j]<=N;i++)f[i*prime[j]]+=mm[i];for(int i=1;i<=N;i++)f[i]+=f[i-1];
}
int main(){init();scanf("%d",&T);while(T--){ans=0;scanf("%d%d",&n,&m);if(n>m) swap(n,m);for(int i=1,j;i<=n;i=j+1){j=min(n/(n/i),m/(m/i));ans+=(f[j]-f[i-1])*(n/i)*(m/i);}printf("%lld\n",ans);}return 0;
}

这篇关于bzoj 2820 莫比乌斯反演的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---