BZOJ

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.