LG P3312 [SDOI2014]数表
Description
有一张 $n imes m$的数表，其第 $i$行第 $j$ 列（$1leq ileq n,1leq jleq m$）的数值为能同时整除 $i$ 和 $j$ 的所有自然数之和。给定 $a$，计算数表中不大于 $a$ 的数之和。
Solution
先无视a的限制,令$T=dx,g(x)=sum_{d|T} sigma(d) mu(frac Td)[d leq a]$
egin{equation}
egin{aligned}
& sum_{i=1}^n sum_{j=1}^m sigma(gcd(i,j))\
= & sum_{d=1}^n sum_{i=1}^{lfloor frac nd
floor} sum_{j=1}^{lfloor frac md
floor}[gcd(i,j)=1]sigma(d)\
= & sum_{d=1}^n sigma(d) sum_{x=1}^{lfloor frac nd
floor} sum_{i=1}^{lfloor frac{n}{dx}
floor} sum_{j=1}^{lfloor frac{m}{dx}
floor}mu(x)\
= & sum_{d=1}^n sigma(d) sum_{x=1}^{lfloor frac nd
floor}mu(x) lfloor frac{n}{dx}
floor lfloor frac{m}{dx}
floor\
= & sum_{T=1}^n lfloor frac nT
floor lfloor frac mT
floor sum_{d|T} sigma(d) mu(frac Td)\
= & sum_{T=1}^n lfloor frac nT
floor lfloor frac mT
floor g(T)
end{aligned}
end{equation}
将所有询问离线下来，以a排序，因为$sigma(d)$仅在$dleq 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 ",ans[i]&((1<<31)-1)); return 0; }