题目描述：
有一张(n imes m)的数表。
其第(i)行第(j)列((1 leq i leq n,1 leq j leq m))的数值为能同时整除(i)和(j)的所有自然数之和。
给定(a)，计算数表中不大于(a)的数之和。
设(d(x))为(x)的因子之和。
写出式子：
(sum_{i=1}^nsum_{j=1}^md(gcd(i,j))(d(gcd(i,j))<=A))
化简：
(sum_{k=1}d(k)(d(k)<=A)sum_{i=1}^{n/k}sum_{j=1}^{m/k}[gcd(i,j)=1])
然后套莫比乌斯函数性质：
(sum_{k=1}^nd(k)(d(k)<=A)sum_{i=1}^{n/k}sum_{j=1}^{m/k}sum_{x|gcd(i,j)}mu(x))
(sum_{k=1}^nd(k)(d(k)<=A)sum_{d=1}^{n/k}mu(x)[n/kd][m/kd])
设(T=kd)，因为(d)和函数名称(d)重复，这里把参数(d)换成(x)，有：
(sum_{T=1}^n[n/T][m/T]sum_{x|T}mu(T/x)d(T/x))
后面这个和(T,A)有关的函数，如果(A)是固定的，可以通过预处理出所有函数(d)，然后只保存小于等于(A)的函数(d)值。
处理出前缀和，询问的时候直接上板子即可。
但是(A)是变化的，怎么办？
考虑将询问离线，按(A)值从小到大排序。
预处理(d(x))函数，按照函数值从小到大排序。
然后随着(A)的变大，不断把新的符合条件的(d(x))插入到树状数组中。
然后用莫比乌斯反演算的时候就是区间求和的过程。
#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+100;
const long long mod=(1ll<<31);
typedef long long ll;
ll vis[maxn],pri[maxn],mu[maxn],sum[maxn],cnt;
ll mm[maxn],mt[maxn],pm[maxn];
int cmp (int x,int y) {
return mm[x]<mm[y];
}
void getMu (int n) {
mu[1]=1;
for (int i=2;i<=n;i++) {
if (!vis[i]) {
mu[i]=-1;
pri[++cnt]=i;
}
for (int j=1;j<=cnt&&i*pri[j]<=n;j++) {
vis[i*pri[j]]=1;
if (i%pri[j]==0) break;
else mu[i*pri[j]]=-mu[i];
}
}
for (int i=1;i<=n;i++) {
for (int j=i;j<=n;j+=i) {
mm[j]+=i;
}
}
for (int i=1;i<=n;i++) pm[i]=i;
sort(pm+1,pm+n+1,cmp);
}
struct query {
int n,m,a,id;
bool operator < (const query &r) const {
return a<r.a;
}
}qq[maxn];
ll c[maxn];//树状数组
int lowbit (int x) {
return x&-x;
}
void up (int p,int v) {
for (int i=p;i<=1e5;i+=lowbit(i)) c[i]+=v,c[i]%=mod;
}
ll getsum (int p) {
ll ans=0;
for (int i=p;i;i-=lowbit(i)) ans=(ans+c[i])%mod;
return ans;
}
ll ans[maxn];
main () {
getMu(1e5);
int q;
scanf("%d",&q);
for (int i=1;i<=q;i++) {
scanf("%d%d%d",&qq[i].n,&qq[i].m,&qq[i].a);
qq[i].id=i;
}
sort(qq+1,qq+q+1);
int tot=1;
int pre=0;
for (int i=1;i<=q;i++) {
while (tot<=1e5) {
if (mm[pm[tot]]<=qq[i].a) {
//up(pm[tot],mm[pm[tot]]);
for (int j=pm[tot];j<=1e5;j+=pm[tot]) {
up(j,1ll*mu[j/pm[tot]]*mm[pm[tot]]%mod);
}
tot++;
}
else {
break;
}
}
if (qq[i].n>qq[i].m) swap(qq[i].n,qq[i].m);
for (int l=1,r;l<=qq[i].n;l=r+1) {
r=min(qq[i].n/(qq[i].n/l),qq[i].m/(qq[i].m/l));
ans[qq[i].id]+=1ll*(qq[i].n/l)*(qq[i].m/l)%mod*(getsum(r)-getsum(l-1)+mod)%mod;
ans[qq[i].id]%=mod;
}
}
for (int i=1;i<=q;i++) printf("%lld
",ans[i]);
}