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 ;
}
這題真是好難啊……