bzoj3994

时间:2023-03-08 16:23:47

智商太低了

详细题解在这里http://blog.****.net/zmoiynlp/article/details/45176129

 const max=;
var u,c,p:array[..max] of longint;
g:array[..max] of int64;
v:array[..max] of boolean;
i,j,t,n,m:longint; function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; function cal(n,m:longint):int64;
var i,j:longint;
begin
i:=;
cal:=;
while i<=min(n,m) do
begin
j:=min(n div (n div i), m div (m div i));
cal:=cal+int64(u[j]-u[i-])*g[n div i]*g[m div i];
i:=j+;
end;
end; begin
u[]:=;
g[]:=;
c[]:=;
for i:= to max do
begin
if not v[i] then
begin
inc(t);
p[t]:=i;
g[i]:=;
c[i]:=;
u[i]:=-;
end;
for j:= to t do
begin
if i*p[j]>max then break;
v[i*p[j]]:=true;
if i mod p[j]= then
begin
g[i*p[j]]:=g[i] div (c[i]+)*int64(c[i]+);
c[i*p[j]]:=c[i]+;
u[i*p[j]]:=;
break;
end;
g[i*p[j]]:=g[i]*;
u[i*p[j]]:=-u[i];
c[i*p[j]]:=;
end;
end;
for i:= to max do
begin
u[i]:=u[i-]+u[i];
g[i]:=g[i-]+g[i];
end;
readln(t);
while t> do
begin
dec(t);
readln(n,m);
writeln(cal(n,m));
end;
end.