莫比乌斯反演

这里有个博客讲的很好：http://www.cnblogs.com/chenyang920/p/4811995.html

这里简要解释解释记录记录下笔记。

首先明确什么是莫比乌斯反演：

这里有一个函数$Fleft( x ight)$，并有另一个函数$Gleft( x ight)$，满足$Gleft( x ight) =sum _{d|x}Fleft( d ight)$，那我们已知$Gleft( x ight)$求$Fleft( x ight)$的过程就是莫比乌斯反演。

具体公式为：$Fleft( x ight) =sum _{d|x}uleft( d ight) ast Gleft( dfrac {x} {d} ight)$ 这里的$uleft( x ight)$可以理解成$Gleft( x ight)$的系数，来控制$Gleft( x ight)$的取值，具体可以看看上面的博客。

$uleft( x ight)$的具体求法可用线性筛实现。

当x可表示成偶数个质数相乘时，$uleft( x ight) =1$

当x可表示成奇数个质数相乘时，$uleft( x ight) =-1$

其余情况则$uleft( x ight) =0$

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<cstdlib>
 5 #include<cmath>
 6 #define N 10005
 7 using namespace std;
 8 bool visit[N];
 9 int n,u[N],prim[N],a,b,c,d,k,qwq,qaq,tot;
10 long long ans;
11 void pre(){
12     memset(visit,false,sizeof(visit));
13     tot=0;
14     u[1]=1;
15     for (int i=2;i<=N;i++){
16         if (!visit[i]){
17             visit[i]=true;
18             prim[++tot]=i;
19             u[i]=-1;
20         }
21         for (int j=1;j<=tot;j++){
22             if (prim[j]*i>N) break;
23             visit[prim[j]*i]=true;
24             if (i%prim[j]) u[prim[j]*i]=-u[i];
25             else break;
26         }
27     }
28 }
29 int main(){
30     memset(u,0,sizeof(u));
31     pre();
32     scanf("%d",&n);
33     while (n--){
34         ans=0;
35         scanf("%d%d%d",&a,&b,&k);
36         if (a>b) swap(a,b);
37         qwq=a/k; qaq=b/k;
38         for (int i=1;i<=qwq;i++)
39          ans+=(long long)u[i]*(long long)(qwq/i)*(long long)(qaq/i);
40         printf("%lld
",ans);
41     }
42     return 0;
43 }

莫比乌斯反演

这里有部分例题的讲解：http://sxysxy.org/blogs/77

莫比乌斯反演的题目有的需要分块求解答案，前缀和维护$uleft( x ight)$，因为考虑到整除的性质，即（i~i+p-1）整除p答案都是一样的，我们可以直接计算这部分的答案。

具体可参考洛谷上的一题：https://www.luogu.org/problem/show?pid=2522

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<cstdlib>
 5 #pragma GCC optamize("O3")
 6 #pragma G++ optamize("O3")
 7 #include<cmath>
 8 #define N 50005
 9 using namespace std;
10 bool visit[N];
11 int n,u[N],prim[N],a,b,c,d,k,qwq,qaq,qoq,qvq,tot,sum[N];
12 long long ans;
13 void pre(){
14     tot=0;
15     sum[1]=1;
16     u[1]=1;
17     for (int i=2;i<=N;i++){
18         if (!visit[i]){
19             prim[++tot]=i;
20             u[i]=-1;
21         }
22         for (int j=1;j<=tot&&prim[j]*i<=N;j++){
23             visit[prim[j]*i]=true;
24             if (i%prim[j]) u[prim[j]*i]=-u[i];
25             else break;
26         }
27         sum[i]=sum[i-1]+u[i];
28     }
29 }
30 long long cale(int l,int r){
31     long long tmp=0;
32     if (l>r) swap(l,r);
33     for (int i=1,go=0;i<=l;i=go+1){   
34      go=min(l/(l/i),r/(r/i));    //从i开始最长的相等区间长度为min(l / (l / i)，r / (r / i)),比如l / (l / i)，设l / i ＝ p，p表示整除时的值，那么l / p就是从i开始整除值为p的个数了
35      tmp+=(l/i)*(r/i)*(sum[go]-sum[i-1]);
36     }
37     return tmp;
38 }
39 int main(){
40     pre();
41     scanf("%d",&n);
42     while (n--){
43         ans=0;
44         scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
45         qwq=b/k;qaq=(a-1)/k;qoq=d/k;qvq=(c-1)/k;
46         for (int i=1;i<=qwq-qaq;i++)
47          ans=cale(qwq,qoq)-cale(qwq,qvq)-cale(qaq,qoq)+cale(qaq,qvq);   //根据容斥原理
48         printf("%lld
",ans);
49     }
50     return 0;
51 }

神奇的代码

但似乎还是会超时......（或许常数过大QAQ）