HDU 1695 BZOJ 2301 莫比乌斯反演

看了两个多小时，大概意思我觉得莫比乌斯是一个利用一个数的能被整除的一些数，通过容斥来计算出这个数的一些信息，很高级。这个题就当做是模板吧。然后把两种形式贴出来：

第一种：

第二种：

然后是容斥的函数：

然后有一些性质：

再耍两道题巩固一下。

#include <cstdio> #include <cstring> #include <vector> #include <cmath> #include <stack> #include <cstdlib> #include <queue> #include <map> #include <iostream> #include <algorithm> #include <bits/stdc++.h>using namespace std; typedef long long LL; const int MAXN = 1000000; bool check[MAXN+10]; int prime[MAXN+10]; int mu[MAXN+10]; void Moblus() {memset(check,false,sizeof(check));mu[1] = 1;int tot = 0;for(int i = 2; i <= MAXN; i++){if( !check[i] ){prime[tot++] = i;mu[i] = -1;}for(int j = 0; j < tot; j++){if(i * prime[j] > MAXN) break;check[i * prime[j]] = true;if( i % prime[j] == 0){mu[i * prime[j]] = 0;break;}else{mu[i * prime[j]] = -mu[i];}}} } int main() {Moblus();LL T,ncas=1;scanf ("%I64d",&T);while (T--){LL a,b,c,d,k;scanf ("%I64d%I64d%I64d%I64d%I64d",&a,&b,&c,&d,&k);if (b>d) swap(b,d);if (k==0){printf ("Case %I64d: 0\n",ncas++);continue;}b/=k;d/=k;LL ans1=0;for (LL i=1;i<=b;i++){ans1+=1ll*mu[i]*(b/i)*(d/i);}LL ans2=0;for (LL i=1;i<=b;i++){ans2+=1ll*mu[i]*(b/i)*(b/i);}printf ("Case %I64d: %I64d\n",ncas++,ans1-ans2/2);}return 0; }

 BZOJ 2301

MDZZ......只能说有毒。。。

#include <cstdio> #include <cstring> #include <vector> #include <cmath> #include <stack> #include <cstdlib> #include <queue> #include <map> #include <iostream> #include <algorithm> #include <bits/stdc++.h>using namespace std; typedef long long LL; const long long MAXN = 1000000; bool check[MAXN+10]; long long prime[MAXN+10]; long long mu[MAXN+10],sum[MAXN+10]; void Moblus() {memset(check,false,sizeof(check));mu[1] = 1;long long tot = 0;for(long long i = 2; i <= MAXN; i++){if( !check[i] ){prime[tot++] = i;mu[i] = -1;}for(long long j = 0; j < tot; j++){if(i * prime[j] > MAXN) break;check[i * prime[j]] = true;if( i % prime[j] == 0){mu[i * prime[j]] = 0;break;}else{mu[i * prime[j]] = -mu[i];}}}sum[0]=0;for (long long i=1;i<=MAXN;i++)sum[i]=mu[i]+sum[i-1]; } LL solve(long long t1,long long t2) {if (t1>t2) swap(t1,t2);LL ans=0;long long j;for (long long i=1;i<=t1;i=j+1){j=min(t1/(t1/i),t2/(t2/i));ans+=1ll*(sum[j]-sum[i-1])*(t1/i)*(t2/i);}return ans; } int main() {Moblus();LL T;int ncas=1;scanf ("%I64d",&T);while (T--){ // printf ("Case %d: ",ncas++); LL a,b,c,d,k;scanf ("%I64d%I64d%I64d%I64d%I64d",&a,&b,&c,&d,&k);b/=k,d/=k;a=ceil(a*1.0/k);c=ceil(c*1.0/k);printf ("%I64d\n",solve(b,d)-solve(a-1,d)-solve(b,c-1)+solve(a-1,c-1));}return 0; }

 

转载于:https://www.cnblogs.com/nj-czy/p/5900161.html

总结

以上是生活随笔为你收集整理的HDU 1695 BZOJ 2301 莫比乌斯反演的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。