给你 $m$ 个询问 , 每个询问包含四个正整数 $l,r,x,y$ , 查询 :

$$\sum\limits^{\infty}_{c=1} \left\lfloor \sqrt{\sum\limits^r_{i=l}\sum\limits^y_{j=x}[\left\lfloor\ \sqrt{\gcd(i,j)} \right\rfloor^2=c]} \right\rfloor^2$$

第一行一个正整数 $m$。
以下 $m$ 行每行四个正整数 $l,r,x,y$ , 意义如上。

每行一个正整数代表答案。

2
1 1 3 3
4 4 9 9

9
30

样例解释 :

$\left\lfloor\ \sqrt{\gcd(i,j)} \right\rfloor^2$ 的表如下 :

样例1	4	5	6	7	8	9
4	4	1	1	1	4	1
5	1	4	1	1	1	1
6	1	1	4	1	1	1
7	1	1	1	4	1	1
8	4	1	1	1	4	1
9	1	1	1	1	1	9

当 $c=1$ 的时候贡献为 $\left\lfloor\ \sqrt{28} \right\rfloor^2=25$。
当 $c=4$ 的时候贡献为 $\left\lfloor\ \sqrt{7} \right\rfloor^2=4$。
当 $c=9$ 的时候贡献为 $\left\lfloor\ \sqrt{1} \right\rfloor^2=1$。总贡献 $30$。

对于 $10$% 的数据 , $1 \leq l,x \leq r,y \leq 10,m=5$。
对于 $50$% 的数据 , $1 \leq l,x \leq r,y \leq 10^2,m \leq 10^5$。
对于 $100$% 的数据 , $1 \leq l,x \leq r,y \leq 5 \times 10^2,m \leq 10^6$。

Uses math;
var
    left,right:array[-1..1000000] of longint;
    i,j,n,m,k,ans:longint;
begin
    read(n,m);
        for i:=1 to m do read(left[i],right[i]);
    for i:=1 to m do
    begin
        k:=right[i]-left[i]+1;
        for j:=m downto 1 do if j<>i then k:=min(k,abs(right[i]-right[j])+abs(left[i]-left[j]));
        inc(ans,k);
    end;
        writeln(ans);
end.

var
    m,i,a,b,c,d:longint;
    sv:text;
begin
    assign(sv,'C:\Users\Administrator\Desktop\Data\Data6.in');rewrite(sv);
    randomize;
    m:=1000000; writeln(sv,m);
    for i:=1 to m do
    begin
        c:=random(500); a:=random(c)+1;
        d:=random(500); b:=random(d)+1;
        writeln(sv,a,' ',b,' ',c,' ',d);
    end;
        close(sv);
end.

Uses math;
Const
    total=500;
var
    bucket:array[-1..total] of longint;
    q,k,i,j,m,a,b,c,d,ans,gcd:longint;
function Alice(a:longint):longint; begin exit(sqr(trunc(sqrt(a)))); end;
begin
    read(m);
    for q:=1 to m do
    begin
        for i:=0 to total do bucket[i]:=0; read(a,b,c,d); ans:=0;
        for i:=a to c do for j:=b to d do
        begin gcd:=0;
            for k:=min(i,j) downto 1 do if (i mod k=0)and(j mod k=0) then begin gcd:=k; break; end;
            gcd:=Alice(gcd);
                        dec(ans,Alice(bucket[gcd]));
                        inc(bucket[gcd]); inc(ans,Alice(bucket[gcd]));
        end;
        writeln(ans);
    end;
end.

Uses math;
Const
    question=1000000+10;
    total=500+10;
var
    point:array[-1..7,-1..question] of longint;
    gcd:array[-1..total,-1..total] of longint;
    bucket:array[-1..total] of longint;
    ans:array[-1..question] of longint;
    i,j,m,a,b,c,d,sum,node_num:longint;
function Alice(a:longint):longint; begin exit(sqr(trunc(sqrt(a)))); end;
function Locate(node:longint):longint;
begin
    if node mod node_num=0 then exit(node div node_num);
    exit(node div node_num+1);
end;
procedure Sort(l,r:longint);
var i,j,s1,s2,s3,s4:longint;
begin
    i:=l; j:=r; s1:=point[5,i]; s2:=point[2,i]; s3:=point[6,i]; s4:=point[4,i];
    repeat
        while (point[5,i]<s1)or((point[5,i]=s1)and(point[2,i]<s2))or((point[5,i]=s1)and(point[2,i]=s2)and(point[6,i]<s3))
        or((point[5,i]=s1)and(point[2,i]=s2)and(point[6,i]=s3)and(point[4,i]<s4)) do inc(i);
        while (point[5,j]>s1)or((point[5,j]=s1)and(point[2,j]>s2))or((point[5,j]=s1)and(point[2,j]=s2)and(point[6,j]>s3))
        or((point[5,j]=s1)and(point[2,j]=s2)and(point[6,j]=s3)and(point[4,j]>s4)) do dec(j);
        if i<=j then begin point[0]:=point[i]; point[i]:=point[j]; point[j]:=point[0]; inc(i); dec(j); end;
    until i>=j;
    if i<r then Sort(i,r); if j>l then Sort(l,j);
end;
procedure Ready;
var i,j,k:longint;
begin
    read(m); node_num:=trunc(sqrt(m));
    for i:=1 to m do
    begin
        point[7,i]:=i; for j:=1 to 4 do read(point[j,i]);
        point[5,i]:=Locate(point[1,i]); point[6,i]:=Locate(point[3,i]);
    end;
    Sort(1,m); a:=1; b:=1; c:=1; d:=1; sum:=1; bucket[1]:=1;
    for i:=1 to total do for j:=1 to total do gcd[i,j]:=1;
    for i:=1 to total do for j:=1 to total do for k:=min(i,j) downto 2 do if (i mod k=0)and(j mod k=0) then begin gcd[i,j]:=Alice(k); break; end;
end;
procedure Transefer(key,l,r,mode:longint);
var i:longint;
begin
    if mode=1 then for i:=l to r do
        begin dec(sum,Alice(bucket[gcd[key,i]]));
        inc(bucket[gcd[key,i]]); inc(sum,Alice(bucket[gcd[key,i]])); end;
    if mode=2 then for i:=l to r do
        begin dec(sum,Alice(bucket[gcd[key,i]]));
        dec(bucket[gcd[key,i]]); inc(sum,Alice(bucket[gcd[key,i]])); end;
end;
begin
    Ready;
    for i:=1 to 2 do begin for j:=1 to 6 do write(gcd[i,j]:3); writeln; end;
    for i:=1 to m do
    begin
        while (c>point[3,i]) do begin Transefer(c,b,d,2); dec(c); end;
        while (c<point[3,i]) do begin inc(c); Transefer(c,b,d,1); end;
        while (d>point[4,i]) do begin Transefer(d,a,c,2); dec(d); end;
        while (d<point[4,i]) do begin inc(d); Transefer(d,a,c,1); end;
        while (a>point[1,i]) do begin Transefer(a,b,d,1); dec(a); end;
        while (a<point[1,i]) do begin inc(a); Transefer(a,b,d,2); end;
        while (b>point[2,i]) do begin Transefer(b,a,c,1); dec(b); end;
        while (b<point[2,i]) do begin inc(b); Transefer(b,a,c,2); end;
        ans[point[7,i]]:=sum;
    end;
    for i:=1 to m do writeln(ans[i]);
end.