莫比乌斯有两种反演形式:
[\begin{array}{l}
f(n) = \sum\limits_{d|n} {u(d)F(\frac{n}{d})} \
f(n) = \sum\limits_{n|d} {u(\frac{d}{n})F(d)}
\end{array}]
最简单筛法
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 int mu[10005];
5 int n=10000;
6 void sieve(){
7 mu[1]=1;
8 for(int i=1;i<=n;i++){
9 for(int j=2*i;j<=n;j+=i){
10 mu[j]-=mu[i];
11 }
12 }
13 }
14 int main(){
15 sieve();
16 for(int i=1;i<=100;i++){
17 cout<<mu[i]<<" ";
18 }
19 }
线性筛法:
1 const int maxn=60000+5;
2 bool vis[maxn];
3 int prime[maxn],mu[maxn];
4 void init_mu(int n){
5 int cnt=0;
6 mu[1]=1;
7 for(int i=2;i<n;i++){
8 if(!vis[i]){
9 prime[cnt++]=i;
10 mu[i]=-1;
11 }
12 for(int j=0;j<cnt&&i*prime[j]<n;j++){
13 vis[i*prime[j]]=1;
14 if(i%prime[j]==0) {mu[i*prime[j]]=0;break;}
15 else { mu[i*prime[j]]=-mu[i];}
16 }
17 }
18 }
《挑战程序设计》例题:没有周期性的字符串函数的计数,用约数的反演形式
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 int mu[10005];
5 int n=10000;
6 void sieve(){
7 mu[1]=1;
8 for(int i=1;i<=n;i++){
9 for(int j=2*i;j<=n;j+=i){
10 mu[j]-=mu[i];
11 }
12 }
13 }
14 int main(){
15 sieve();
16 while(cin>>n){
17 int res=0;
18 for(int i=1;i<=n;i++){
19 if(n%i==0){
20 res+=mu[n/i]*pow(26,i);
21 }
22 }
23 cout<<res<<endl;
24 }
25 }
hdu1695 gcd
解法一:转化成gcd=1,用倍数的反演形式
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 int mu[1050500];
5 int n=1000000;
6 void sieve(){
7 mu[1]=1;
8 for(int i=1;i<=n;i++){
9 for(int j=2*i;j<=n;j+=i){
10 mu[j]-=mu[i];
11 }
12 }
13 }
14 int main(){
15 sieve();
16 ll t,a,b,c,d,k,ans1,ans2;
17 cin>>t;
18 for(int i=1;i<=t;i++){
19 ans1=ans2=0;
20 cin>>a>>b>>c>>d>>k;
21 if(b>d) swap(b,d);
22 if(k==0){
23 printf("Case %d: 0\n",i);
24 continue;
25 }
26 b/=k,d/=k;
27 for(int j=1;j<=b;j++){
28 ans1+=mu[j]*(b/j)*(d/j);
29 }
30 for(int j=1;j<=b;j++){
31 ans2+=mu[j]*(b/j)*(b/j);
32 }
33 printf("Case %d: %lld\n",i,ans1-ans2/2);
34 }
35 return 0;
36 }
解法二:其实是一种思路,就是直接运用莫比乌斯反演公式,,只是想自己多练习一下而已。
1 #include<bits/stdc++.h>
2 using namespace std;
3 typedef long long ll;
4 int mu[1050500];
5 int n=1000000;
6 void sieve(){
7 mu[1]=1;
8 for(int i=1;i<=n;i++){
9 for(int j=2*i;j<=n;j+=i){
10 mu[j]-=mu[i];
11 }
12 }
13 }
14 int main(){
15 sieve();
16 ll t,a,b,c,d,k,ans1,ans2;
17 cin>>t;
18 for(int i=1;i<=t;i++){
19 ans1=ans2=0;
20 cin>>a>>b>>c>>d>>k;
21 if(b>d) swap(b,d);
22 if(k==0){
23 printf("Case %d: 0\n",i);
24 continue;
25 }
26 for(int j=k;j<=b;j+=k){
27 ans1+=(ll)mu[j/k]*(b/j)*(d/j);
28 }
29 for(int j=k;j<=b;j+=k){
30 ans2+=(ll)mu[j/k]*(b/j)*(b/j);//注意加括号
31 }
32 printf("Case %d: %lld\n",i,ans1-ans2/2);
33 }
34 return 0;
35 }
原文链接: https://www.cnblogs.com/elpsycongroo/p/7252171.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/257588
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!