BZOJ 2190


先分析一下题目给的图,发现这张图中有三条永远那么长的线和两个对称的区域,所以答案就是其中一个对称的区域中能看到的人数*2+3


一竖列一竖列来考虑

首先,对于点$(i,j)$,能看到的条件是$gcd(i,j)=1$,否则还能看到$(\frac{i}{gcd(i,j)},\frac{j}{gcd(i,j)})$等点,显然它们共线,矛盾

对于第$i$列,能看到的点数即为$gcd(i,j)=1(j\in[2,i-1])$的数量,就是说在$[2,i-1]$内与$i$互质的数的数量,也就是$\varphi(i-1)$

然后求欧拉函数就好了(这一篇先扯线性筛法)

先用筛法求素数,然后根据求出的素数利用欧拉函数的性质来求,用到的性质如下:

  • 若x为素数,则$\varphi(x)=x-1$

  • 若$a,b$互质,则$\varphi(a*b)=\varphi(a)*\varphi(b)$

  • 若b为质数且$a\ mod\ b=0$,则$\varphi(a*b)=\varphi(a)*b$

没了,有啥问题看代码吧

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
program bzoj_2190;
var phi,p:array[1..40000]of longint;
n,cnt,i,j,ans:longint;
prime:array[1..40000]of boolean;
begin
readln(n);
fillchar(prime,sizeof(prime),true);
cnt:=0;
for i:=2 to n do
begin
if prime[i] then
begin
inc(cnt);
p[cnt]:=i;
phi[i]:=i-1;
end;
for j:=1 to cnt do
begin
if i*p[j]>=n then break;
prime[i*p[j]]:=false;
if i mod p[j]=0 then
begin
phi[i*p[j]]:=phi[i]*p[j];
break;
end else phi[i*p[j]]:=phi[i]*(p[j]-1);
end;
end;
ans:=0;
for i:=2 to n-1 do inc(ans,phi[i]);
writeln(ans*2+3);
end.