本站于2023年9月4日。收到“大连君*****咨询有限公司”通知
说我们IIS7站长博客，有一篇博文用了他们的图片。
要求我们给他们一张图片6000元。要不然法院告我们
为避免不必要的麻烦，IIS7站长博客，全站内容图片下架、并积极应诉
博文内容全部不再显示，请需要相关资讯的站长朋友到必应搜索。谢谢！
另祝：版权碰瓷诈骗团伙，早日弃暗投明。
相关新闻：借版权之名、行诈骗之实，周某因犯诈骗罪被判处有期徒刑十一年六个月
叹！百花齐放的时代,渐行渐远!
Description
有一张 $n\times m$的数表，其第 $i$行第 $j$ 列（$1\leq i\leq n,1\leq j\leq m$）的数值为能同时整除 $i$ 和 $j$ 的所有自然数之和。给定 $a$，计算数表中不大于 $a$ 的数之和。
Solution
先无视a的限制,令$T=dx,g(x)=\sum_{d|T} \sigma(d) \mu(\frac Td)[d \leq a]$
\begin{equation}
\begin{aligned}
& \sum_{i=1}^n \sum_{j=1}^m \sigma(gcd(i,j))\\
= & \sum_{d=1}^n \sum_{i=1}^{\lfloor \frac nd \rfloor} \sum_{j=1}^{\lfloor \frac md \rfloor}[gcd(i,j)=1]\sigma(d)\\
= & \sum_{d=1}^n \sigma(d) \sum_{x=1}^{\lfloor \frac nd \rfloor} \sum_{i=1}^{\lfloor \frac{n}{dx} \rfloor} \sum_{j=1}^{\lfloor \frac{m}{dx} \rfloor}\mu(x)\\
= & \sum_{d=1}^n \sigma(d) \sum_{x=1}^{\lfloor \frac nd \rfloor}\mu(x) \lfloor \frac{n}{dx}\rfloor \lfloor \frac{m}{dx} \rfloor\\
= & \sum_{T=1}^n \lfloor \frac nT \rfloor \lfloor \frac mT \rfloor \sum_{d|T} \sigma(d) \mu(\frac Td)\\
= & \sum_{T=1}^n \lfloor \frac nT \rfloor \lfloor \frac mT \rfloor g(T)
\end{aligned}
\end{equation}
将所有询问离线下来，以a排序，因为$\sigma(d)$仅在$d\leq a$时有贡献，所以每次处理时随着a的增大有一些d加入了贡献，使用树状数组统计答案。
取模自然溢出
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int q,tree[100005],sig[100005],mu[100005],prime[100005],tot,cnt=1,ans[20005];
bool vst[100005];
struct Node
{
int n,m,a,id;
}node[20005];
struct S
{
int d,v;
}s[100005];
inline int read()
{
int f=1,w=0;
char ch=0;
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
w=(w<<1)+(w<<3)+ch-'0';
ch=getchar();
}
return f*w;
}
bool cmp(Node x,Node y)
{
return x.a<y.a;
}
bool cmp2(S x,S y)
{
return x.v<y.v;
}
int lowbit(int x)
{
return x&-x;
}
int add(int pos,int v)
{
while(pos<=100000)
{
tree[pos]+=v;
pos+=lowbit(pos);
}
}
int query(int pos)
{
int ret=0;
while(pos)
{
ret+=tree[pos];
pos-=lowbit(pos);
}
return ret;
}
int main()
{
for(int i=1;i<=100000;i++)
for(int j=i;j<=100000;j+=i)
sig[j]+=i;
for(int i=1;i<=100000;i++)
s[i]=(S){i,sig[i]};
sort(s+1,s+100001,cmp2);
mu[1]=1;
for(int i=2;i<=100000;i++)
{
if(!vst[i])
{
prime[++tot]=i;
mu[i]=-1;
}
for(int j=1;j<=tot&&i*prime[j]<=100000;j++)
{
vst[i*prime[j]]=true;
if(!(i%prime[j]))
break;
mu[i*prime[j]]=-mu[i];
}
}
q=read();
for(int i=1;i<=q;i++)
{
node[i]=(Node){read(),read(),read(),i};
if(node[i].n>node[i].m)
swap(node[i].n,node[i].m);
}
sort(node+1,node+q+1,cmp);
for(int i=1;i<=q;i++)
{
int N=node[i].n,M=node[i].m;
for(;s[cnt].v<=node[i].a&&cnt<=100000;cnt++)
for(int j=s[cnt].d;j<=100000;j+=s[cnt].d)
add(j,s[cnt].v*mu[j/s[cnt].d]);
for(int j=1;j<=N;)
{
int k=min(N/(N/j),M/(M/j));
ans[node[i].id]+=(N/j)*(M/j)*(query(k)-query(j-1));
j=k+1;
}
}
for(int i=1;i<=q;i++)
printf("%d\n",ans[i]&((1<<31)-1));
return 0;
}
[SDOI2014]数表
