题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3529
挺恶心的数论TAT。。。
设f[i]是i的约数和，这个可以nln(n)扫出来。
ans=∑d[n/d]*[m/d]*∑i|d f[i]*μ[d/i]
然后由于只有f[i]<=a是有用的，所以对给的a从小到大排序，对求的f[i]从小到大排序，用个树状数组维护一下。
由于分块思想，可以枚举d，然后会出现一段n/i是一样的，所以把那部分区间求和就可以了。
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cstdio>
#define rep(i,l,r) for (int i=l;i<=r;i++)
#define down(i,l,r) for (int i=l;i>=r;i--)
#define clr(x,y) memset(x,y,sizeof(x))
#define inf 1000000009
#define ll long long
#define maxn 100500
#define mm 2147483648
#define low(x) (x&(-x))
using namespace std;
struct data{int a,n,m,b,id;
}a[maxn];
struct node{int a;int b;
}f[maxn];
int tot,mx,T,b[maxn],pri[maxn],mu[maxn],ans[maxn];
int t[maxn];
int read(){
int x=,f=; char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-; ch=getchar();}
while (isdigit(ch)){x=x*+ch-''; ch=getchar();}
return x*f;
}
bool cmpa(data a,data b){
return a.a<b.a;
}
bool cmp(node a,node b){
return a.a<b.a;
}
void pre(){
mu[]=;
rep(i,,mx){
if (!b[i]) b[i]=,pri[++tot]=i,mu[i]=-;
rep(j,,tot)if (i*pri[j]<=mx){
b[i*pri[j]]=;
if (i%pri[j]==) {mu[i*pri[j]]=; break;}
else mu[i*pri[j]]=-mu[i];
}
else break;
}
rep(i,,mx)
for (int j=i;j<=mx;j+=i) f[j].a+=i;
rep(i,,mx) f[i].b=i;
}
void add(int x,int y){
while (x<=mx){
t[x]+=y; x+=low(x);
}
}
int ask(int x){
int ans=;
while (x){
ans+=t[x];
x-=low(x);
}
return ans;
}
void solve(int id){
int n=a[id].n,m=a[id].m;
for (int i=,j;i<=n;i=j+){
j=min(n/(n/i),m/(m/i));
ans[a[id].id]+=(n/i)*(m/i)*(ask(j)-ask(i-));
}
}
int main(){
int q=read();
rep(i,,q){
a[i].n=read(); a[i].m=read(); a[i].a=read(); a[i].id=i;
if (a[i].n>a[i].m) swap(a[i].n,a[i].m);
mx=max(mx,a[i].n);
}
pre();
sort(a+,a++q,cmpa);
sort(f+,f++mx,cmp);
int now=;
rep(i,,q){
while (f[now].a<=a[i].a&&now<=mx){
for (int j=f[now].b;j<=mx;j+=f[now].b){
add(j,f[now].a*mu[j/f[now].b]);
}
now++;
}
solve(i);
}
rep(i,,q) printf("%d\n",ans[i]&0x7fffffff);
return ;
}