题解 P2158 【[SDOI2008]仪仗队】
Smallbasic
2019-12-12 11:35:40
这还真是道神题。。。
考虑点(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;
}
```