仪仗队(points)
【题意】
求存在多少个i,j互质的二元组(i,j)(0<=i,j<=n)
【输入】
一个数字表示n(n<=40000)
【输出】
一个数字,表示有多少个满足条件的二元组
枚举2到4000,对于每一个求其欧拉函数,求和乘二+3
program points; var n,i,j,k,tot,ans:longint; prime:array [0..10001] of longint; yes:array [0..40001] of boolean; begin assign(input,'points.in'); reset(input); assign(output,'points.out'); rewrite(output); read(n); dec(n); tot:=0; fillchar(yes,sizeof(yes),false); for i:=2 to n do if not yes[i] then begin inc(tot); prime[tot]:=i; yes[i]:=true; for j:=i to n div i do yes[i*j]:=true; end; ans:=0; for i:=2 to n do begin k:=i; j:=1; while (j<=tot)and(prime[j]<=i) do begin if i mod prime[j] = 0 then k:=k*(prime[j]-1) div (prime[j]); inc(j); end; ans:=ans+k; end; ans:=ans*2+3; writeln(ans); close(input); close(output); end.