题意：给定整数N，求1<=x,y<=N且Gcd(x,y)为素数的
数对(x,y)有多少对
1<=N<=10^7
思路：莫比乌斯反演，同BZOJ2820……
const max=;
var sum:array[..max]of int64;
prime,flag,f,mu:array[..max]of longint;
n,m,i,j,t,v,cas:longint; function clac(n:longint):int64;
var x,i,pos:longint;
begin
clac:=; i:=;
while i<=n do
begin
x:=n div i;
pos:=n div x;
clac:=clac+(sum[pos]-sum[i-])*x*x;
i:=pos+;
end;
end; begin mu[]:=;
for i:= to max do
begin
if flag[i]= then
begin
inc(m); prime[m]:=i;
mu[i]:=-;
end;
j:=;
while (j<=m)and(prime[j]*i<=max) do
begin
t:=prime[j]*i; flag[t]:=;
if i mod prime[j]= then
begin
mu[t]:=; break;
end;
mu[t]:=-mu[i];
inc(j);
end;
end;
for i:= to m do
for j:= to max div prime[i] do
begin
t:=prime[i]*j;
f[t]:=f[t]+mu[j];
end;
for i:= to max do sum[i]:=sum[i-]+f[i];
read(n);
writeln(clac(n)); end.
惊奇地发现，自己两年前用欧拉函数的方法过掉了此题……
From hzwer
枚举每个素数，然后每个素数p对于答案的贡献就是（1 ~ n / p） 中有序互质对的个数
而求1~m中有序互质对x，y的个数，可以令y >= x, 当y = x时，有且只有y = x = 1互质，当y > x时，确定y以后符合条件的个数x就是phiy
所以有序互质对的个数为（1 ~ n/p）的欧拉函数之和乘2减1（要求的是有序互质对，乘2以后减去（1， 1）多算的一次）
那么就只需要先筛出欧拉函数再求个前缀和就可以了
var b,prime,phi:array[..]of longint;
s:array[..]of int64;
ans:int64;
i,j,m,n:longint; begin readln(n);
b[]:=; phi[]:=;
for i:= to n do
begin
if b[i]= then
begin
inc(m); prime[m]:=i; phi[i]:=i-;
end;
for j:= to m do
begin
if i*prime[j]>n then break;
b[i*prime[j]]:=;
if i mod prime[j]= then
begin
phi[i*prime[j]]:=phi[i]*prime[j];
break;
end
else phi[i*prime[j]]:=phi[i]*(prime[j]-); end;
end; for i:= to n do s[i]:=s[i-]+phi[i];
for i:= to m do ans:=ans+s[n div prime[i]]*-;
writeln(ans); end.