[SDOI2008] 仪仗队
暴力的想法，枚举每个点，判断它是否能被看到。
然后就思考能被看到的充要条件。
假设队列是坐标区间 $[0,n)$ 的区域，如果横纵坐标都不为 0，那么当且仅当横纵坐标互质时能被看到，反之不能。
原因很简单，如果两坐标不互质，将两坐标除以最大公约数就能得到另一个在这条直线上且更靠近原点的点，一定能把该点遮盖，反之则一定能看见。
算上 $(0,1)$ 和 $(1,0)$ 两点，就是我们的答案。
所以有：
$$
\begin{aligned}
Ans=&\sum_{i=1}^{n-1}\sum_{j=1}^{n-1}[\gcd(i,j)=1]+2
\end{aligned}
$$
直接反演应该不用多说：
$$Ans=\sum_{k=1}\mu(k)\left\lfloor\dfrac{n-1}{k}\right\rfloor^2+2$$
另外我们根据欧拉函数的定义：不大于 $n$ 的与 $n$ 互质的数个数，可以将原式变形为另外的状态。
这样就有：
$$\dfrac{1}{2}(Ans-1)=\sum_{i=1}^{n-1}\varphi(i)$$
实际上我只是单纯地想写：
$$\sum_{i=1}^{n-1}\varphi(i)=\sum_{i=1}^{n-1}\sum_{j=1}^{i}[\gcd(i,j)=1]$$
然后左右调整一下就是上面的那个。
于是我们就有：
$$
Ans=2\sum_{i=1}^{n-1}\varphi(i)+1
$$
反正线性筛之后都可以 $O(n)$ 求，差别不大。
闲着没事可以杜教筛 $O(n^{2/3})$，两种方式好像复杂度仍然没有区别，只不过第二种方法更适合杜教筛（毕竟只要求一个前缀和）。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| #include<iostream>
#include<cstdio>
#define ll __int128
using namespace std;
namespace Ehnaev{
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
return ret*f;
}
inline void write(ll x) {
static char buf[22];static ll len=-1;
if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
while(len>=0) putchar(buf[len--]);
}
}using Ehnaev::read;using Ehnaev::write;
const ll N=2e6;
ll n,cnt;
ll prime[N+5],mu[N+5],smu[N+5];
bool f[N+5];
inline void Init() {
f[1]=1;mu[1]=1;
for(ll i=2;i<=n;i++) {
if(!f[i]) {prime[++cnt]=i;mu[i]=-1;}
for(ll j=1;j<=cnt&&i*prime[j]<=n;j++) {
f[i*prime[j]]=1;
if(i%prime[j]==0) {
mu[i*prime[j]]=0;break;
}
mu[i*prime[j]]=-mu[i];
}
}
for(ll i=1;i<=n;i++) smu[i]=smu[i-1]+mu[i];
}
int main() {
n=read();Init();n--;
ll ans=2;
for(ll i=1,j;i<=n;i=j+1) {
j=n/(n/i);ans=ans+(smu[j]-smu[i-1])*(n/i)*(n/i);
}
if(n==0) write(0);
else write(ans);
return 0;
}
|