BZOJ 2818

$gcd(x,y)=k,k$为素数说明$gcd(\frac{x}{k},\frac{y}{k})=1$ 这样欧拉函数就粗线了…

枚举每个素数,然后每个素数$p$对于答案的贡献就是$[1,n\ div\ p]$中互质对的个数

包括$y$的数对$(x,y)\ (x\in[1,y])$中的互质对个数即为$\varphi(y)$,所以$[1,x]$中互质对个数就是$2*\varphi(x)-1$(-1是因为$(1,1)$算了两次)

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
program bzoj_2818;
var p:array[1..10000000]of longint;
prime:array[1..10000000]of boolean;
phi:array[1..10000000]of int64;
n,i,j,cnt:longint;
ans:int64;
procedure calc;
begin
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;
end;
begin
readln(n);
calc;
for i:=2 to n do inc(phi[i],phi[i-1]);
for i:=1 to n do phi[i]:=phi[i]<<1+1;
ans:=0;
for i:=1 to cnt do inc(ans,phi[n div p[i]]);
writeln(ans);
end.