题解 P2158 【[SDOI2008]仪仗队】

Smallbasic

2019-12-12 11:35:40

Solution

这还真是道神题。。。 考虑点(x,y)在什么情况下$\color{red}\text{不会}$被看到 由于是从(1,1)开始看,视线应该是点A(0,0)和点B(x,y)的连线,表示为函数: $$f(i)={y\over x}i$$ 如果(x,y)不会被看到,那么这条线上一定有横纵坐标皆为整数的点,且它的横坐标小于x。 设这个点为$C(x',y')$ $$\because y'\in Z,y'={y\over x}x'$$ $$\therefore {yx'\over x}\in Z$$ 显然有一组解为$({x\over gcd(x,y)},{y\over gcd(x,y)})$ 所以点$(x,y)$一定能被$({x\over gcd(x,y)},{y\over gcd(x,y)})$挡住。 而又有: $${x\over gcd(x,y)}\le x, {y\over gcd(x,y)}\le y$$ 两等号成立当且仅当$x\perp y$。而当等号成立时,就成了自己挡住自己,显然是可以被看到的。 所以得出结论:点(x,y)当且仅当$x\perp y$时会被看到。 原问题转化为求: $$\sum_{i=0}^{n-1} \sum_{j=0}^{n-1} [gcd(i,j)==1]$$ 为了方便假设k就是$n-1$ 由于$gcd(0,i)=i$,所以原式等于: $$\sum_{i=1}^k\sum_{j=1}^k [gcd(i,j)==1]$$ 又因为$gcd(i,j)=gcd(j,i)$~~废话~~,所以: $$=2\cdot\sum_{i=1}^k\sum_{j=1}^{i-1} [gcd(i,j)==1]+1$$ 之所以上面加的是1是因为前面那坨式子或漏掉点(1,1)。 我们会发现后面那坨恰好是$\phi(i)$。 因此式子变为: $$2\cdot\sum_{i=1}^{k}\phi(i)+3$$ 考虑如何求$\sum_{i=1}^{k}\phi(i)$ 还是为了适应我的习惯设$m$为$k$ 先引入一个~~没什么~~概念:卷积: 若: $$h(n)=\sum_{d|n}f(d)g(\lfloor{n\over d}\rfloor)$$ 则称$h$是$f$和$g$的卷积,写作$h=f\cdot g$ 回到题目 众所周知: $$(\phi\cdot 1)(n)=\sum_{d|n}\phi(d)=n$$ 记$h=\phi\cdot1$ $$\sum_{i=1}^m h(i)=\sum_{i=1}^m\sum_{d|i}\phi(d)$$ $$\sum_{i=1}^m h(i)=\sum_{i=1}^m\sum_{j=1}^{\lfloor{m\over i}\rfloor}\phi(d)$$ 这一步如果不容易理解的话可以把省略掉的函数1提出来,看成交换求和号后的式子。 设: $$S(n)=\sum_{i=1}^n \phi(i)$$ 上式变为: $$\sum_{i=1}^m h(i)=\sum_{i=1}^mS({\lfloor{m\over i}\rfloor})$$ $$\sum_{i=1}^m h(i)=\sum_{i=2}^mS({\lfloor{m\over i}\rfloor})+S(m)$$ $$S(m)=\sum_{i=1}^m h(i)-\sum_{i=2}^mS({\lfloor{m\over i}\rfloor})$$ 我们知道$h(i)=(\phi\cdot1)(i)=i$,有: $$\sum_{i=1}^m h(i)=\sum_{i=1}^m i={m^2+m\over2}$$ 即是: $$S(m)={m^2+m\over2}-\sum_{i=2}^mS({\lfloor{m\over i}\rfloor})$$ 最终答案是: $$2S(n-1)+1$$ 后面整除分块的话时间复杂度大概是: $$\Theta(\sum_{i=1}^n\sqrt{\lfloor{n\over i}\rfloor})=\Theta(\int_{i=1}^n\sqrt{\lfloor{n\over i}\rfloor}di)=\Theta(n^{2\over3})$$ 应该是最优解了吧,数据范围完全可以到MAX_INT。 对了注意的是求$S(m)$要先预处理出前几千的$S(m)$,这样会更快。 还有其实快速求$\phi$前缀和的这个算法叫做杜教筛,不清楚可以去模版学习一下。 代码(记住1要特判): ```cpp #include <iostream> #include <cstdio> #include <algorithm> #include <cstring> #include <map> using namespace std; typedef long long ll; map<int, ll> sphi; bool notprime[5001]; int t, n, prime[5001], top = 0; ll phi[5001]; inline void pre() { phi[1] = 1; for (register int i = 2; i <= 5000; ++i) { if (!notprime[i]) prime[++top] = i, phi[i] = i - 1; for (register int j = 1; j <= top; ++j) { if (i * prime[j] > 5000) break; notprime[i * prime[j]] = 1; if (!(i % prime[j])) { phi[i * prime[j]] = phi[i] * prime[j]; break; } else phi[i * prime[j]] = phi[i] * (prime[j] - 1); } } for (register int i = 2; i <= 5000; ++i) phi[i] += phi[i - 1]; } ll calcphi(int n) { if (n <= 5000) return phi[n]; if (sphi[n]) return sphi[n]; ll rt = (ll)n * (ll)(n + 1) / 2; for (register unsigned int l = 2, r; l <= n; l = r + 1) { r = n / (n / l); rt -= (r - l + 1) * calcphi(n / l); } return sphi[n] = rt; } int main() { scanf("%d", &n); pre(); if (n == 1) printf("0"); else printf("%lld", 2 * calcphi(n - 1) + 1); return 0; } ```