$$ans=\sum^{n}_{i=1}\sum^{m}_{j=1}lcm(i,j)$$

\begin{gather*} &ans=\sum^{n}_{i=1}\sum^{m}_{j=1}\frac{ij}{gcd(i,j)}\\ &ans=\sum^{n}_{d=1}\sum^{m}_{i=1}\sum^{n}_{j=1}\frac{ij}{d}[gcd(i,j)==d]\\ &ans=\sum^{n}_{d=1}\frac{1}{d}\sum^{m}_{i=1}i\sum^{n}_{j=1}j[gcd(i,j)==d]\\ \end{gather*} \begin{gather*} 设f(n,d)=\sum^{n}_{i=1}i\sum^{m}_{j=1}j[gcd(i,j)==d]\\ 设F(n,d)=\sum^{n}_{i=1}i\sum^{m}_{j=1}j[d|gcd(i,j)]\\ \end{gather*} \begin{align*} F(n,d)&=d^2\frac{(\lfloor\frac{n}{d}\rfloor+1)*\lfloor\frac{n}{d}\rfloor*(\lfloor\frac{m}{d}\rfloor+1)*\lfloor\frac{m}{d}\rfloor}{4} \\ 由莫比乌&斯反演得f(n,d)=\sum^{\frac{n}{d}}_{x=1}\mu(x)*F(n,dx)\\ f(n,d)&=\sum^{\frac{n}{d}}_{x=1}\mu(x)*d^2*x ^2\frac{(\lfloor\frac{n}{d}\rfloor+1)*\lfloor\frac{n}{d}\rfloor*(\lfloor\frac{m}{d}\rfloor+1)*\lfloor\frac{m}{d}\rfloor}{4}\\ \end{align*} \begin{gather*} ans=\sum^{n}_{d=1}\frac{1}{d}\sum^{\frac{n}{d}}_{x=1}\mu(x)*d^2*x ^2\frac{(\lfloor\frac{n}{dx}\rfloor+1)*\lfloor\frac{n}{dx}\rfloor*(\lfloor\frac{m}{dx}\rfloor+1)*\lfloor\frac{m}{dx}\rfloor}{4}\\ ans=\sum^{n}_{T=1}\frac{(\lfloor\frac{n}{T}\rfloor+1)*\lfloor\frac{n}{T}\rfloor*(\lfloor\frac{m}{T}\rfloor+1)*\lfloor\frac{m}{T}\rfloor}{4}\sum_{d|T}d*\mu(\frac{T}{d})*(\frac{T}{d})^2\\ ans=\sum^{n}_{T=1}\frac{(\lfloor\frac{n}{T}\rfloor+1)*\lfloor\frac{n}{T}\rfloor*(\lfloor\frac{m}{T}\rfloor+1)*\lfloor\frac{m}{T}\rfloor}{4}\sum_{d|T}(\frac{T}{d})*\mu(d)*d^2\\ ans=\sum^{n}_{T=1}\frac{(\lfloor\frac{n}{T}\rfloor+1)*\lfloor\frac{n}{T}\rfloor*(\lfloor\frac{m}{T}\rfloor+1)*\lfloor\frac{m}{T}\rfloor}{4}\sum_{d|T}(\frac{T}{d})*\mu(d)*d^2\\ 设g(T)=\sum_{d|T}(\frac{T}{d})*\mu(d)*d^2\\ g(T)=T\sum_{d|T}\mu(d)*d\\ ans=\sum^{n}_{T=1}\frac{(\lfloor\frac{n}{T}\rfloor+1)*\lfloor\frac{n}{T}\rfloor*(\lfloor\frac{m}{T}\rfloor+1)*\lfloor\frac{m}{T}\rfloor}{4}g(T)\\ \end{gather*}

对于该表达式可以用线性筛预处理出一个前缀和,然后使用整除分块处理每个询问。

代码：

#include <bits/stdc++.h>

const int MAXN = 1e7,MOD = 100000009;

using namespace std;

int T,n,m,cnt,inv;
long long f[MAXN+5],p[MAXN+5];
bool vis[MAXN+5];

inline long long pow_mod(long long a,long long b){
    long long ret = 1;
    while(b){
        if(b&1) ret = ret * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    ret %= MOD;
    return ret;
}

inline void init(){
    f[1] = 1;
    for(int i = 2;i <= MAXN;i++){
        if(!vis[i]){
            p[++cnt] = i;
            f[i] = (i-1ll*i*i%MOD+MOD)%MOD;
        }
        for(int j = 1;j <= cnt&&p[j]*i <= MAXN;j++){
            vis[i*p[j]] = true;
            if(i%p[j] == 0){
                f[i*p[j]] = f[i]*p[j]%MOD;
                break;
            }
            else f[i*p[j]] = f[i]*f[p[j]]%MOD;
        }
    }        
    for(int i = 2;i <= MAXN;i++) {
        f[i] = f[i] + f[i-1];
        f[i] %= MOD;
    }    
}

int main()
{
    inv = pow_mod(4,99328719);
    init();
    //printf("%d",f[MAXN]);
    scanf("%d",&T);
    while(T--){
        scanf("%d %d",&n,&m);

        long long ret,ans = 0,R;
        for(long long i = 1;i <= min(n,m);i = R + 1)
        {
            R = min(n/(n/i),m/(m/i));
            ret = f[R] - f[i-1];
            ans += 1LL*(n/i)*(n/i+1)%MOD*(m/i)%MOD*(m/i+1)%MOD*ret%MOD*inv%MOD;
            ans %= MOD;
        }
        ans %= MOD;
        ans += MOD;
        ans %= MOD;
        printf("%lld\n",ans);        
    }

    return 0;
}