[SDOI2014]数表
题目描述
有一张 \(n\times m\) 的数表，其第 \(i\) 行第 \(j\) 列（\(1\le i\le n\)，\(1\le j\le m\)）的数值为能同时整除 \(i\) 和 \(j\) 的所有自然数之和。给定 \(a\)，计算数表中不大于 \(a\) 的数之和。
\(1\le n,m\le 10^5\)，\(1\le Q\le 2\times 10^4\)。
思路点拨
我们先考虑对于两个数 \(i,j\) ,那些数才会同时整除 \(i,j\) 。显然这些数都是 \(i,j\) 的公约数。我们定义 \(f(x)\) 表示 \(x\) 的约数和，即 \(\sum_{d|x}d\) 。对于 \(i,j\) 而言，满足条件的数是 \(f(\gcd(i,j))\) 。这一点很好理解。我们先不看 \(a\) 的约束，那么答案就是：
\[\sum_{i=1}^n \sum_{j=1}^m f(\gcd(i,j))
\]
\[\sum_{d=1}^n f(d)\sum_{i=1}^n \sum_{j=1}^m [\gcd(i,j)=d]
\]
\[\sum_{d=1}^n f(d)\sum_{i=1}^{\lfloor \frac{n}{d}\rfloor} \sum_{j=1}^{\lfloor \frac{m}{d}\rfloor} [\gcd(i,j)=1]
\]
\[\sum_{d=1}^n f(d) \sum_{k=1}^{\lfloor \frac{n}{d}\rfloor} \mu(k) \lfloor \dfrac{n}{dk}\rfloor \dfrac{m}{dk}\rfloor
\]
我们；令 \(T=kd\) ,那么
\[\sum_{T=1}^n \lfloor \dfrac{n}{T}\rfloor \lfloor \dfrac{m}{T}\rfloor( \sum_{d|T} f(d)\mu(\dfrac{T}{d}))
\]
这个式子需要富比尼定理优化。可以 \(O(\sqrt n)\) 计算，前提是后边括号内的式子在 \(O(n \log n)\) 的时间预处理。
但是这道题目还没有写完，因为有 \(a\) 的至于限制，所以原式准确表达为：
\[\sum_{T=1}^n \lfloor \dfrac{n}{T}\rfloor \lfloor \dfrac{m}{T}\rfloor( \sum_{d|T} f(d)\mu(\dfrac{T}{d})[f(d) \leqslant a])
\]
我们可以将全部的询问离线，按照 \(a\) 为关键字排序，每一次就将 \(f(x) \leqslant a\) 的 \(f(x)\) 从 \(0\) 设为它本身的值。我们富比尼定理计算上面的式子的时候，\(g(x)=\sum_{d|T} f(d)\mu(\dfrac{T}{d})\) ,需要以区间的形式计算，所以我们还需要使用一个树状数组来进行单点修改，区间加和。
时间复杂度 \(O(n \log^2 n+q\sqrt n \log n)\) 。
放出一份代码:
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-f;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
const int mod=(1ll<<31);
int T;
const int MAXN=1e5+10,N=1e5;
struct node{
int x,id;
bool friend operator<(const node &A,const node &B){
return A.x<B.x;
}
}f[MAXN];
struct getans{
int x,y,w;
int id;
bool friend operator<(const getans &A,const getans &B){
return A.w<B.w;
}
}q[MAXN];
int ans[MAXN],mu[MAXN];
bool vis[MAXN];
void init(){
for(int i=1;i<=N;i++){
f[i].id=i;
mu[i]=1;
for(int j=i;j<=N;j+=i)
f[j].x+=i;
}
sort(f+1,f+N+1);
for(int i=2;i<=N;i++){
if(vis[i]) continue;
mu[i]=-1;
for(int j=i*2;j<=N;j+=i){
vis[j]=1;
mu[j]=-mu[j];
if(j%(i*i)==0) mu[j]=0;
}
}
}
int g[MAXN];
int lowbit(int x){
return x&(-x);
}
void add(int x,int w){
for(int i=x;i<=N;i+=lowbit(i))
g[i]=(g[i]+w)%mod;
}
int query(int x){
int cnt=0;
for(int i=x;i;i-=lowbit(i))
cnt=(cnt+g[i])%mod;
return cnt;
}
signed main(){
init();
int T=read();
for(int i=1;i<=T;i++){
q[i].x=read(),q[i].y=read(),q[i].w=read();
q[i].id=i;
}
sort(q+1,q+T+1);
int last=1;
for(int i=1;i<=T;i++){
while(last<=N&&f[last].x<=q[i].w){
int d=f[last].id;
for(int T=d;T<=N;T+=d)
add(T,(f[last].x*mu[T/d]+mod*100)%mod);
last++;
}
int l=1,r=0,n=q[i].x,m=q[i].y;
while(l<=min(n,m)){
r=min(n/(n/l),m/(m/l));
ans[q[i].id]=(ans[q[i].id]+(query(r)-query(l-1)+mod)*(n/l)%mod*(m/l))%mod;
l=r+1;
}
}
for(int i=1;i<=T;i++) cout<<ans[i]<<endl;
return 0;
}