Description
Input
一个正整数T表示数据组数
接下来T行 每行两个正整数 表示N、M
Output
T行 每行一个整数 表示第i组数据的结果
Sample Input
1
4 5
Sample Output
122
HINT
T <= 10000
N, M<=10000000
题解君：http://hi.baidu.com/mikeni2006/item/b4f78a4520de9bab61d7b985
看了一上午才看懂，最后终于在lazycal的帮助下想出来了
我们需要先预处理出那个奇怪的前缀和就是
d Σ d* Σ d'*μ(d') i=1 d'|d
然后因为trunc(n/i)和trunc(m/i)都只有根号级别个值，也就是只要枚举这些值就行了
为了跑得快，类型用的longint，然后写了很多int64函数
const
maxn=;
h=;
var
flag:array[..maxn]of boolean;
f,s:array[..maxn]of longint;
p:array[..]of longint;
t,n,m,tot:longint; function max(x,y:longint):longint;
begin
if x>y then exit(x);
exit(y);
end; function min(x,y:longint):longint;
begin
if x<y then exit(x);
exit(y);
end; function get(a:longint):longint;
begin
exit(((int64(a)*a+a)>>)mod h);
end; procedure pre;
var
i,j:longint;
begin
f[]:=;
for i:= to do
begin
if flag[i]=false then
begin
inc(tot);
p[tot]:=i;
f[i]:=-i+h;
end;
for j:= to tot do
begin
if int64(p[j])*i> then break;
flag[p[j]*i]:=true;
if i mod p[j]= then
begin
f[p[j]*i]:=f[i];
break;
end
else f[p[j]*i]:=int64(f[i])*f[p[j]]mod h;
end;
end;
for i:= to do
s[i]:=(int64(s[i-])+int64(f[i])*i)mod h;
end; procedure main;
var
i,j,t,li,ri,lj,rj,l,r,ans:longint;
begin
read(n,m);
if n>m then
begin
t:=n;n:=m;m:=t;
end;
ans:=;
i:=;
while sqr(i)<=n do
begin
ans:=(int64(ans)+((int64(f[i])*i mod h)*get(trunc(n/i))mod h)*get(trunc(m/i)))mod h;
inc(i);
end;
j:=trunc(m/i);
i:=trunc(n/i);
while (i>) and (j>) do
begin
ri:=trunc(n/i);
li:=trunc(n/(i+))+;
lj:=trunc(m/(j+))+;
rj:=trunc(m/j);
l:=max(li,lj);
r:=min(ri,rj);
if l<=r then ans:=(int64(ans)+(int64(s[r]-s[l-]+h)*get(i)mod h)*get(j))mod h;
if ri<=rj then dec(i)
else dec(j);
end;
writeln(ans);
end; begin
pre;
read(t);
while t> do
begin
dec(t);
main;
end;
end.