[文章目录]
Description
有一张N×m的数表，其第i行第j列（1<=i<=n，1<=j<=m）的数值为能同时整除i和j的所有自然数之和。给定a，计算数表中不大于a的数之和。1<=N,m<=10^5，1<=Q<=2×10^4
设f[x]表示x的约数和，n<=m。推导：
枚举gcd
=
=
=
枚举k*d=>D
=
前半部分对于每个询问分块。
后半部分，f[x]的初值为0，树状数组维护关于D的前缀和，对于询问按照a排序，将f[x]合法的x的倍数D进行修改。
时间复杂度
注：取模为2^31好像普遍方法用unsigned int，【long long TLE了】
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 101000
typedef unsigned int ll;
ll f[N];
bool cmp(int x,int y){return f[x]<f[y];}
int mu[N],pri[N],cnt,ran[N];
int Min(int x,int y){return x<y ? x:y;}
bool v[N];
void initialize()
{
for(int i=1;i<=100000;++i)
for(int j=i;j<=100000;j+=i) f[j]+=i;
for(int i=1;i<=100000;++i) ran[i]=i;
sort(ran+1,ran+100000+1,cmp);
mu[1]=1;
for(int i=2;i<=100000;++i)
{
if(!v[i]) pri[++cnt]=i,mu[i]=-1;
for(int j=1;i*pri[j]<=100000&&j<=cnt;++j)
{
v[i*pri[j]]=1;
if(i%pri[j]) mu[i*pri[j]]=-mu[i];
else break;
}
}
}
struct node
{
int n,m,id; ll w;
}a[21000];
bool cmp1(node x,node y){return x.w<y.w;}
ll g[101000];
void fix(int x,ll y) {while(x<=100000) g[x]+=y,x+=-x&x;}
ll query(int x) {ll re=0; while(x>0) re+=g[x],x-=-x&x; return re;}
void Fix(int x)
{
for(int i=x;i<=100000;i+=x) if(mu[i/x])
fix(i,f[x]*mu[i/x]);
}
ll ans[21000];
int main()
{
initialize();
int t; scanf("%d",&t);
for(int i=1;i<=t;++i)
{
scanf("%d%d%u",&a[i].n,&a[i].m,&a[i].w);
if(a[i].n>a[i].m) swap(a[i].n,a[i].m);
/*ll tmp=0;
for(int d=1;d<=a[i].n;++d)
{
ll tmp1=0;
for(int k=1;k<=d;++k) if(d%k==0&&f[k]<=a[i].w) tmp1+=f[k]*mu[d/k];
tmp+=tmp1*(a[i].n/d)*(a[i].m/d);
}
printf("%lld\n",tmp);*/
a[i].id=i;
}
sort(a+1,a+t+1,cmp1);
ll n,m,now=1,d,e;
for(int i=1;i<=t;++i)
{
while(now<=100000&&f[ran[now]]<=a[i].w) Fix(ran[now]),now++;
d=1; n=a[i].n; m=a[i].m;
while(d<=n)
{
e=Min(n/(n/d),m/(m/d));
ans[a[i].id]=(ans[a[i].id]+(n/d)*(m/d)*(query(e)-query(d-1)));
d=e+1;
}
}
for(int i=1;i<=t;++i) printf("%u\n",ans[i]&0x7fffffff);
return 0;
}