NOI 2016 循环之美 (莫比乌斯反演+杜教筛)

题目大意：略洛谷传送门鉴于洛谷最近总崩，附上良心LOJ链接

任何形容词也不够赞美这一道神题

$\sum\limits_{i=1}^{N}\sum\limits_{j=1}^{M}[gcd(i,j)==1][gcd(j,K)==1]$

$\sum\limits_{j=1}^{M}[gcd(j,K)==1]\sum\limits_{i=1}^{N}[gcd(i,j)==1]$

我们先处理右边的式子$\sum\limits_{i=1}^{N}[gcd(i,j)==1]$：

$\sum\limits_{i=1}^{N}\sum\limits_{d|gcd(i,j)}\mu(d)\sum\limits_{j=1}^{M}[gcd(j,K)==1][d|j]$

$\sum\limits_{d=1}^{N}\mu(d)\left \lfloor \frac{N}{d} \right \rfloor \sum\limits_{j=1}^{M}[gcd(j,K)==1][d|j]$

$\sum\limits_{d=1}^{N}\mu(d)\left \lfloor \frac{N}{d} \right \rfloor \sum\limits_{j=1}^{\left \lfloor \frac{M}{d} \right \rfloor}[gcd(jd,K)==1]$

加下来就是比较关键的一个展开式子，[gcd(jd,K)==1]是[gcd(d,K)==1]&[gcd(j,K)==1]的充分必要条件：

$\sum\limits_{d=1}^{N}[gcd(d,K)==1]\mu(d)\left \lfloor \frac{N}{d} \right \rfloor \sum\limits_{j=1}^{\left \lfloor \frac{M}{d} \right \rfloor}[gcd(j,K)==1]$

84分算法：

令$f(n)=\sum\limits_{i=1}^{n}[gcd(i,K)==1]$

这是啥？

欧拉函数$\varphi$啊！别和我一样反演傻了连欧拉函数的定义都忘了

$f(n)=\left \lfloor \frac{n}{K} \right \rfloor \varphi(K) + \sum\limits_{i=1}^{n\;mod\;K}[gcd(i,K)==1]$

预处理出$\varphi(K)$和$\sum\limits_{i=1}^{n}[gcd(i,K)==1]$，那么$f(n)$就能在$O(1)$求得

可$\sum\limits_{i=1}^{n}[gcd(i,K)==1]\mu(d)$就不能用$\varphi$了，但经过计算，$g$数组能在大约$O(n*K的质因子个数)$的时间内处理出来，极限情况也只不超过$2.6 \cdot 10^{7}$

那么这个问题就在$O(n)$的时间内被解决了

蒟蒻的代码写得非常迷就不放了

100分算法：

这是一道神仙题

先放上原式：$\sum\limits_{d=1}^{N}[gcd(d,K)==1]\mu(d)\left \lfloor \frac{N}{d} \right \rfloor \sum\limits_{j=1}^{\left \lfloor \frac{M}{d} \right \rfloor}[gcd(j,K)==1]$

$\sum\limits_{j=1}^{\left \lfloor \frac{M}{d} \right \rfloor}[gcd(j,K)==1]$可以用$84$分算法里的方法预处理，每次$O(1)$得到

现在令$g(N,K)=\sum\limits_{i=1}^{N}[gcd(i,K)==1]\mu(i)$

$=\sum\limits_{i=1}^{N}\mu(i)*\sum\limits_{d|i}\mu(d)$

$=\sum\limits_{d|K}\mu(d) \sum\limits_{i=1}^{N} [d|i]\mu(i)$

$=\sum\limits_{d|K}\mu(d) \sum\limits_{i=1}^{\left \lfloor \frac{N}{d} \right \rfloor} \mu(id)$

关键的部分来了

如果两个数$gcd(x,y)==1$，说明它们没有公共因子，满足积性函数的性质，那么$\mu(xy)=\mu(x)\mu(y)$

反之它们存在公共因子，那么$\mu(xy)$一定等于$0$

利用这个性质

$=\sum\limits_{d|K}\mu(d)^{2} \sum\limits_{i=1}^{\left \lfloor \frac{N}{d} \right \rfloor} [gcd(i,d)==1]\mu(i)$

诶！右面这个东西$\sum\limits_{i=1}^{\left \lfloor \frac{N}{d} \right \rfloor} [gcd(i,d)==1]\mu(i)$，似乎就是$g(\left \lfloor \frac{N}{d} \right \rfloor,d)$啊！

递归求解即可

当$n==0$是，答案就是$0$

发现$K==1$时不能继续递归了否则会死循环，此时

$G(n,1)=\sum\limits_{i=1}^{n} [gcd(i,1)==1]\mu(i)=\sum\limits_{i=1}^{n} \mu(i)$

$n$可能很大，上杜教筛即可

 #include <map>

 #include <cmath>

 #include <vector>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #define N1 20000010

 #define M1 2000010

 #define K1 2010

 #define ll long long

 #define dd double

 #define cll const long long

 #define it map<int,int>::iterator

 using namespace std;

 int N,M,K,maxn;

 int mu[N1],smu[N1],pr[M1],cnt,phik; bool use[N1];

 int f[K1],ps[K1],son[K1],is[K1],pn,sn;

 vector<int>ss[K1];

 void Pre()

 {

     int i,j,x; mu[]=smu[]=;

     for(i=;i<=maxn;i++)

     {

         if(!use[i]){ pr[++cnt]=i; mu[i]=-;}

         for(j=;j<=cnt&&i*pr[j]<=maxn;j++)

         {

             use[i*pr[j]]=;

             if(i%pr[j]){ mu[i*pr[j]]=-mu[i];}

             else{ break; }

         }

         smu[i]=smu[i-]+mu[i];

     }

     for(son[++sn]=,x=K,phik=K,i=;i<=K;i++)

     {

         if(x%i==){ ps[++pn]=i; phik=phik/i*(i-); while(x%i==) x/=i; }

         if(K%i==){ son[++sn]=i; }

     }

     for(j=;j<=pn;j++)

         for(i=ps[j];i<=K;i+=ps[j]) is[i]=;

     for(i=;i<=K;i++) f[i]=f[i-]+(is[i]?:);

     for(i=;i<=sn;i++)

     {

         x=son[i];

         for(j=;j<=x;j++)

             if(x%j==&&mu[j]) ss[x].push_back(j);

     }

 }

 map<int,int>mp;

 ll Smu(int n)

 {

     if(n<=maxn) return smu[n];

     it k=mp.find(n);

     if(k!=mp.end()) return k->second;

     int i,la;ll ans=;

     for(i=;i<=n;i=la+)

     {

         la=n/(n/i);

         ans-=1ll*Smu(n/i)*(la-i+);

     }

     mp[n]=ans;

     return ans;

 }

 ll F(int x){return 1ll*(x/K)*phik+f[x%K];}

 ll G(int n,int k)

 {

     if(!n) return ;

     if(k==)

     {

         if(n<=maxn) return smu[n];

         else return Smu(n);

     }

     int i,d;ll ans=;

     for(i=;i<ss[k].size();i++)

     {

         d=ss[k][i];

         ans+=1ll*G(n/d,d);

     }

     return ans;

 }

 int main()

 {

     scanf("%d%d%d",&N,&M,&K);

     int i,j,la; ll ans=; maxn=min(max(N,M),); Pre();

     for(i=;i<=min(N,M);i=la+)

     {

         la=min(N/(N/i),M/(M/i));

         ans+=1ll*(G(la,K)-G(i-,K))*(N/i)*F(M/i);

     }

     printf("%lld\n",ans);

     return ;

 }

巴特西

NOI 2016 循环之美 (莫比乌斯反演+杜教筛)

84分算法：

100分算法：

最新文章

热门文章