Time Limit: 1000 ms Memory Limit: 512 MB
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
(n,m≤10^5,Q≤2∗10^4)
solution
(a)的限制很烦，但其实如果最后式子推出来的话，我们可以离线来处理
那就先看去掉这个限制的问题怎么解决咯
先把式子列出来
然后前面下取整的东西分块搞定就好了，(g(t))的话，因为可以通过枚举约数来求，复杂度是根号的，所以就直接枚举来求就好了，(mu)的话可以筛出来，那么……
考虑(f)怎么求
有个约数和定理
(f)的话首先是个积性函数，我们在筛(mu)的时候想顺便把这个也筛出来
考虑(f(d))的值，如果说(d)是质数的话答案显然是(d+1)，下面讨论(d)为合数的情况
设(d=i * p)，其中(p)为质数
-
(p mid i)，那么(p)和(i)互质，所以(f(d) = f(p) * f(i))
-
(pmid i)，设(i = t * p^x) ，那么根据约数和定理，我们可以得
[f(i*p) = f(t)f(p^{x+1}) = f(t)sumlimits_{i=0}^{x+1}p^i ]然后我们把(p^0)（也就是1）拿出来，得到
[f(i * p) = f(t) + f(t)*sumlimits_{i=1}^{x+1}p^i = f(t) + f(t)*f(p^x)*p ]然后(i = t * p^x)，所以(f(t) * f(p^x) = f(i))
所以最后就是(f(d) = f(t) + f(i) * p)
然后就可以筛出(f(d))啦
剩下的东西
现在加上(a)的限制，其实就是离线处理
我们先将所有的询问按照(a)的大小排序，然后从小到大处理
因为分块的时候我们要用到的是(g(x))的前缀和，所以用一个树状数组来处理
将(f(x))排个序，枚举的时候只枚举到(f(x)<a)，然后枚举另一个约数求出(g)，丢到树状数组里面去
求答案的时候直接查询就好了
others
这题的话如果直接取模会被卡常。。因为模数很特殊所以可以自然溢出来取模，最后记得给ans&上一个2147483647
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int MAXN=1e5+10;
const int MOD=2147483647;
struct Q{
int id,n,m,a;
friend bool operator <(Q x,Q y)
{return x.a<y.a;}
}q[MAXN];
int miu[MAXN],g[MAXN],p[MAXN],f[MAXN],loc[MAXN];
ll c[MAXN];
int ans[MAXN];
bool vis[MAXN];
int n,m,T,maxn,a,pos,nowans;
int prework(int n);
int ksm(int x,int y);
int add(int x,ll delta);
ll query(int x);
bool cmp(int x,int y){return f[x]<f[y];}
int main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
scanf("%d",&T);
maxn=0;
for (int i=1;i<=T;++i){
scanf("%d%d%d",&q[i].n,&q[i].m,&q[i].a);
q[i].id=i;
if (q[i].n>q[i].m) swap(q[i].n,q[i].m);
maxn=max(maxn,q[i].n);
}
prework(maxn);
sort(q+1,q+1+T);
for (int i=1;i<=maxn;++i) loc[i]=i;
sort(loc+1,loc+1+maxn,cmp);
int now=1;
for (int o=1;o<=T;++o){
n=q[o].n;
m=q[o].m;
a=q[o].a;
while (now<=maxn&&f[loc[now]]<=a){
for (int t=1;t*loc[now]<=maxn;++t)
add(t*loc[now],f[loc[now]]*miu[t]);
++now;
}
nowans=pos=0;
for (int i=1;i<=n;i=pos+1){
pos=min(n/(n/i),m/(m/i));
nowans+=(n/i)*(m/i)*(query(pos)-query(i-1));
}
ans[q[o].id]=nowans&MOD;
}
for (int i=1;i<=T;++i) printf("%lld
",ans[i]);
}
int prework(int n){
miu[1]=1; f[1]=1;
memset(vis,false,sizeof(vis));
int cnt=0,tmp,tot;
for (int i=2;i<=n;++i){
if (!vis[i]){
p[++cnt]=i;
miu[i]=-1;
f[i]=i+1;
}
for (int j=1;j<=cnt&&p[j]*i<=n;++j){
vis[i*p[j]]=true;
if (i%p[j]){
miu[i*p[j]]=-miu[i];
f[i*p[j]]=f[i]*(1+p[j]);
}
else{
miu[i*p[j]]=0;
tmp=i;tot=1;
while (tmp%p[j]==0) tmp/=p[j];
f[i*p[j]]=f[tmp]+p[j]*f[i];
}
}
}
}
int add(int x,ll delta){
for (;x<=maxn;x+=x&-x)
c[x]+=delta;
}
ll query(int x){
ll ret=0;
for (;x;x-=x&-x)
ret+=c[x];
return ret;
}