$$\begin{aligned} & \sum\limits^n_{i=1} \sum\limits^m_{j=1} \sigma(\gcd(i,j)) \\ = & \sum\limits^{\min\{n,m\}}_{k=1} \sum\limits^n_{i=1} \sum\limits^m_{j=1} \sigma(k) [\gcd(i,j)=k] \\ = & \sum\limits^{\min\{n,m\}}_{k=1} \sum\limits^{\left\lfloor\frac{n}{k}\right\rfloor}_{i=1} \sum\limits^{\left\lfloor\frac{m}{k}\right\rfloor}_{j=1} \sigma(k) [\gcd(i,j)=1] \\ = & \sum\limits^{\min\{n,m\}}_{k=1} \sum\limits^{\left\lfloor\frac{n}{k}\right\rfloor}_{i=1} \sum\limits^{\left\lfloor\frac{m}{k}\right\rfloor}_{j=1} \sigma(k) \sum\limits_{d|\gcd(i,j)} \mu(d) \\ = & \sum\limits^{\min\{n,m\}}_{k=1} \sigma(k) \sum\limits^{\min\{\left\lfloor\frac{n}{k}\right\rfloor,\left\lfloor\frac{m}{k}\right\rfloor\}}_{d=1} \mu(d) \sum\limits^{\left\lfloor\frac{n}{k}\right\rfloor}_{i=1} \sum\limits^{\left\lfloor\frac{m}{k}\right\rfloor}_{j=1} [d|i][d|j] \\ = & \sum\limits^{\min\{n,m\}}_{k=1} \sigma(k) \sum\limits^{\min\{\left\lfloor\frac{n}{k}\right\rfloor,\left\lfloor\frac{m}{k}\right\rfloor\}}_{d=1} \mu(d) \left\lfloor\frac{n}{kd}\right\rfloor\left\lfloor\frac{m}{kd}\right\rfloor \\ = & \sum\limits^{\min\{n,m\}}_{k=1} \sigma(k) \sum\limits^{\min\{\left\lfloor\frac{n}{k}\right\rfloor,\left\lfloor\frac{m}{k}\right\rfloor\}}_{d=1} \mu(d) \left\lfloor\frac{n}{kd}\right\rfloor\left\lfloor\frac{m}{kd}\right\rfloor \\ = & \sum\limits^{\min\{n,m\}}_{T=1} \left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{m}{T}\right\rfloor \sum\limits_{d|T} \sigma(d) \mu(\frac T d) \end{aligned}$$

• 第 $7$ 部转化 : 用了 $\text{Crash}$ 的千层套路。

由于有 $[\sigma(\gcd(i,j))\leq a]$ 的贡献在这里 , 所以这个东西不能直接拆成 $\sigma=\sum\limits_{d|\gcd(i,j)} d$ , 不然这题就太水了。

我们设 $f(T)=\sum\limits_{d|T} \sigma(d) \mu(\frac T d)$ , 然后考虑一个有用的贡献定义为 $[\sigma(d) \leq a]$ 。 所以说询问离线以后 , 每当一个 $a$ 变大 , 那么就会对 $\sigma(a)$ 有影响 , 然后我们要将 $f(ad) [d \in \left\lfloor \frac n a \right\rfloor]$ 的值改变 , 这个东西总共就是 $n \log_e n$ 的 , 那么运用线段树就可以做到 $O(n \log_e n \log_2 n)$。

考虑提前筛 $\sigma$ 和 $\mu$ ? 暴力 $O(n \log n)$ 即可。

查询的时候的复杂度就是 $O(qn^{\frac{1}{2}} \log n)$。

Uses math;
Const
    total=12;
var
    ans,sigma,mobius:array[-1..total] of longint;
    input:array[-1..total,-1..6] of longint;
    tree:array[-1..total << 4] of longint;
    i,j,k,n,m,a,id,anss,test:longint;
procedure Swap(var a,b:longint);var t:longint;begin t:=a; a:=b; b:=t; end;
procedure Sort(l,r,a,b,c,d:longint);
var i,j,s:longint;
begin
    i:=l; j:=r; s:=input[(l+r) >> 1,a];
    repeat
        while input[i,a]<s do inc(i);
        while input[j,a]>s do dec(j);
        if i<=j then
        begin
            Swap(input[i,a],input[j,a]); Swap(input[i,b],input[j,b]);
            Swap(input[i,c],input[j,c]); Swap(input[i,d],input[j,d]);
            inc(i); dec(j);
        end;
        until i>=j;
    if i<r then Sort(i,r,a,b,c,d); if j>l then Sort(l,j,a,b,c,d);
end;
procedure Insert(l,r,k,key,add:longint);
var mid:longint;
begin
    if l=r then begin inc(tree[k],add); exit; end; mid:=(l+r) >> 1;
    if key<=mid then Insert(l,mid,k << 1,key,add) else Insert(mid+1,r,k << 1+1,key,add);
    tree[k]:=tree[k << 1]+tree[k << 1+1];
end;
function Query(l,r,k,x,y:longint):longint;
var mid:longint;
begin
    if (l>=x)and(y>=r) then exit(tree[k]); mid:=(l+r) >> 1; Query:=0;
    if x<=mid then inc(Query,Query(l,mid,k << 1,x,y));
    if y>mid then inc(Query,Query(mid+1,r,k << 1+1,x,y));
end;
begin
    read(test);
    for i:=1 to test do begin read(input[i,1],input[i,2],input[i,3]); input[i,4]:=i; end;
    Sort(1,test,3,1,2,4); mobius[1]:=1; a:=0;
    for i:=1 to total do for j:=1 to total div i do inc(sigma[i*j],i);
    for i:=1 to total do for j:=2 to total div i do dec(mobius[i*j],mobius[i]);
    for i:=1 to total do begin input[i,5]:=i; input[i,6]:=sigma[i]; end;
    Sort(1,test,6,5,0,0);
    for k:=1 to test do
    begin
        while a<input[k,3] do begin inc(a); id:=input[a,5];
        for i:=2 to total div id do Insert(1,total,1,i*id,sigma[id]*mobius[i]); end;
        anss:=0; i:=1; j:=0; n:=input[k,1]; m:=input[k,2];
        repeat
            j:=min(n div (n div i),m div (m div i));
            inc(anss,(n div i)*(m div i)*(Query(1,n,1,i-1,j))); i:=j+1;
        until i>min(n,m);
        ans[input[k,4]]:=anss;
    end;
    for i:=1 to test do writeln(ans[i]);
end.