Description
有一张N×M的数表，其第i行第j列（1<=i <=N，1<=j<=M）的数值为能同时整除i和j的所有自然数之和。给定a，计算数表中不大于a的数之和。
Input
输入包含多组数据。
输入的第一行一个整数Q表示测试点内的数据组数，接下来Q行，每行三个整数n，m，a(|a| < =10^9)描述一组数据。
Output
对每组数据，输出一行一个整数，表示答案模2^31的值。
Sample Input
2
4 4 3
10 10 5
Sample Output
20
148
HINT
1<=N，M<=10^5 ， 1<=Q<=2×10^4
题目大意：令F(i)为i的约数和，多次询问对于1<=x<=n,1<=y<=m,F(gcd(x,y))<=a的所有数对(x,y)，求ΣF(gcd(x,y))%(2^31)。
题解：
语文题系列，还数表什么的……
这是一道神题，综合了好多东西。首先，根据题目大意，如果不考虑有a的限制，那么令g(i)为1<=x<=n,1<=y<=m,gcd(x,y)=i的数的个数，
则
再用线性筛预处理F(i)，得
那么求出
的前缀和，即暴力枚举i的倍数进行计算，然后在O(NlogN)内可出解。
那么现在有了a的限制怎么办呢？
对答案有贡献的只有F(i)<=a的i，那么我们将询问按照a从小到大排序，将F(i)从小到大排序，每次询问将<=a的F(i)暴力插入，用树状数组来维护这个前缀和，时间复杂度O(nlog^2n+q√nlogn)。
还有一点，要%（2^31）,其实不用long long，自然溢出即可，最后&一下INT_MAX即可。
代码如下：
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<string.h>
#include<math.h>
#define ll long long
#define inf 0x7f7f7f7f
#define lb(x) (x&-x)
#define N 100005
using namespace std;
ll read()
{
ll x=,f=;
char c=getchar();
while(c>'9' || c<'0') {if(c=='-') f=-;c=getchar();}
while(c<='9' && c>='0') {x=x*+c-'0';c=getchar();}
return x*f;
}
int t,n,m,a,mx;
struct que
{
int n,m,a,id;
que(){}
que(int a_,int b,int c,int d):n(a_),m(b),a(c),id(d){}
inline bool operator<(const que& rhs) const{return a<rhs.a;}
}T[];
struct nod
{
int fv,v;
inline bool operator<(const nod& rhs) const{return v<rhs.v;}
}f[N];
int mu[N],prime[N],tot,c[N],ans[N];
bool exist[N];
void init()
{
mu[]=;
int tmp;
for(int i=;i<=mx;i++)
{
if(!exist[i])
{
mu[i]=-;
prime[++tot]=i;
}
for(int j=;j<=tot&&(tmp=prime[j]*i)<=mx;j++)
{
exist[tmp]=;
if(i%prime[j]==)
{
mu[tmp]=;
break;
}
mu[tmp]=-mu[i];
}
}
for(int i=;i<=mx;i++)
{
f[i].fv=i;
for(int j=i;j<=mx;j+=i) f[j].v+=i;
}
}
void add(int x,int v)
{
while(x<=mx)
{
c[x]+=v;
x+=lb(x);
}
}
int query(int x)
{
int ret=;
while(x)
{
ret+=c[x];
x-=lb(x);
}
return ret;
}
void solve(int n,int m,int &ans)
{
ans=;
for(int i=;i<=n;i++)
{
int las=min((n/(n/i)),(m/(m/i)));
ans+=(n/i)*(m/i)*(query(las)-query(i-));
ans&=;
i=las;
}
}
int main()
{
t=read();
for(int i=;i<=t;i++)
{
n=read(),m=read(),a=read();
if(n>m) swap(n,m);
T[i]=que(n,m,a,i);
mx=max(mx,n);
}
init();
sort(T+,T+t+);sort(f,f+mx+);
int now=;
for(int i=;i<=t;i++)
{
while(f[now+].v<=T[i].a && now+<=mx)
{
now++;
for(int j=f[now].fv;j<=mx;j+=f[now].fv)
add(j,f[now].v*mu[j/f[now].fv]);
}
solve(T[i].n,T[i].m,ans[T[i].id]);
}
for(int i=;i<=t;i++) printf("%d\n",ans[i]);
return ;
}
这题真是好难啊……