Luogu

LOJ

分析

先不考虑 $a$ 的限制，则答案为
$$
\begin{aligned}
&\sum_{i=1}^n\sum_{j=1}^m\sigma(\gcd(i,j))\\
=&\sum_{i=1}^n\sum_{j=1}^m\sum_{d|i,d|j}d\\
=&\sum_{d=1}^nd\left\lfloor\frac{n}{d}\right\rfloor\left\lfloor\frac{m}{d}\right\rfloor
\end{aligned}
$$
然而这样子并不好处理 $a$ 的限制，所以我们考虑把 $\mathbf{id}$ 还原为 $\mu*\sigma$，即
$$
\sum_{d=1}^n\left(\sum_{k|d}\sigma(k)\mu\left(\frac{d}{k}\right)\right)\left\lfloor\frac{n}{d}\right\rfloor\left\lfloor\frac{m}{d}\right\rfloor
$$
这样子可以发现，我们只要把 $\leq a$ 的 $\sigma(k)$ 的贡献设成 $\sigma(k)$、$> a$ 的 $\sigma(k)$ 的贡献设为 $0$ 就可以算出正确答案了。

于是只要把所有询问按 $a$ 排序，然后将 $\sigma(k)$ 从小到大加入即可。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10,L=100000;

int p[N],v[N],cnt=0;
int mu[N],sigma[N],sd[N],pd[N];
void sieve(int n) {
    sigma[1]=mu[1]=1;
    for (int i=2;i<=n;++i) {
        if (!v[i]) p[++cnt]=i,mu[i]=-1,sigma[i]=sd[i]=i+1,pd[i]=i;
        for (int j=1;j<=cnt&&i*p[j]<=n;++j) {
            v[i*p[j]]=1;
            if (i%p[j]) {
                mu[i*p[j]]=-mu[i];
                sigma[i*p[j]]=sigma[i]*(p[j]+1);
                pd[i*p[j]]=p[j],sd[i*p[j]]=p[j]+1;
            } else {
                pd[i*p[j]]=pd[i]*p[j],sd[i*p[j]]=sd[i]+pd[i*p[j]];
                sigma[i*p[j]]=sigma[i]/sd[i]*sd[i*p[j]];
            }
        }
    }
}

int Q,id[N],ans[N];
struct query { int n,m,a,id; } q[N];
bool operator <(query a,query b) { return a.a<b.a; }

int c[N];
void add(int x,int y) { for (;x<=L;x+=x&-x) c[x]+=y; }
int sum(int x) { int s=0; for (;x;x-=x&-x) s+=c[x]; return s; }

int main() {
    sieve(L);
    for (int i=1;i<=L;++i) id[i]=i;
    sort(id+1,id+L+1,[](int x,int y) { return sigma[x]<sigma[y]; });
    Q=read();
    for (int i=1;i<=Q;++i) q[i]=(query){read(),read(),read(),i};
    sort(q+1,q+Q+1);
    for (int i=1,j=1;i<=Q;++i) {
        while (j<=L&&sigma[id[j]]<=q[i].a) {
            for (int k=id[j];k<=L;k+=id[j])
                if (mu[k/id[j]]) add(k,sigma[id[j]]*mu[k/id[j]]);
            ++j;
        }
        int n=q[i].n,m=q[i].m; if (n>m) swap(n,m);
        if (n>m) swap(n,m);
        for (int l=1,r;l<=n;l=r+1) {
            r=min(n/(n/l),m/(m/l));
            ans[q[i].id]+=(sum(r)-sum(l-1))*(n/l)*(m/l);
        }
    }
    for (int i=1;i<=Q;++i) {
        if (ans[i]<0) ans[i]+=2147483648;
        printf("%d\n",ans[i]);
    }
    return 0;
}