BZOJ3529 [SDOI2014]数表

题意

有一张$n \times m$的数表,其第$i$行第$j$列($1 \leqslant i \leqslant n,1 \leqslant j \leqslant m$)的数值为能同时整除$i$和$j$的所有自然数之和。给定$a$,计算数表中不大于$a$的数之和。

多组数据,数据组数为$T$。
$1 \leqslant n,m \leqslant 1e5,T \leqslant 2e4$。

题解

设$f(i)$为$i$的约数和。这东西我是$O(n\ln{n})$计算的,似乎可以线性筛?
原题要求的其实是这样的一个式子:
$$\sum_{i=1}^{n}\sum_{j=1}^{m}f(gcd(i,j)) \times [gcd(i,j) \leqslant a]$$
这个$a$的条件似乎很麻烦,先忽视掉这个$a$。
于是式子变成
$$\sum_{i=1}^{n}\sum_{j=1}^{m}f(gcd(i,j))$$
考虑枚举两数的$gcd$,运用一下莫比乌斯反演,那么式子又可以变成
$$\sum_{i=1}^{n}\sum_{i|d}\mu(\frac{d}{i})\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor f(i)$$
然后可以把$\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor$提到前面去,式子变成
$$\sum_{i=1}^{n}\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{i}\rfloor\sum_{d|i}f(d)\mu(\frac{i}{d})$$

$$F(i)=\sum_{d|i}f(d)\mu(\frac{i}{d})$$
那么我们只要能预处理出$F(i)$的前缀和,那么利用整除分块,我们就可以在$O(\sqrt{n})$解决单次了。
但是我们还忽视了一个问题,那就是关于$a$的限制。其实这个问题不难解决。将所有询问离线后,按照$a$从小到大来排序。再将$i$按照$f(i)$来排序,每次$a$的值增加了以后,就维护一下$F(i)$的值就可以了。
但还有一个问题,$F(i)$的前缀和修改。不能直接$O(n)$来做,因此还要用树状数组来维护$F(i)$的前缀和。
是道很好的题,然而想到把$\lfloor\frac{n}{d}\rfloor\lfloor\frac{m}{d}\rfloor$提到前面去之后,就不知道怎么做了。后面还用树状数组维护也算是神了……
时间复杂度$O(q(\log q+\sqrt{n})+n\log n \ln n)$。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int INF=1e9;
const long double eps=1e-9;
const int maxn=1e5+10;
const int maxt=2e4+10;
int mu[maxn],prime[maxn],vis[maxn],p[maxn];
unsigned int bit[maxn],Ans[maxt];
struct node{
int n,m,a,id;
};
struct node query[maxt];
bool cmp(const node &lhs,const node &rhs){
return lhs.a<rhs.a;
}
unsigned int sum[maxn];
bool compr(const int &lhs,const int &rhs){
return sum[lhs]<sum[rhs];
}
inline int read(){
int x=0,flag=1;
char ch=getchar();
while(!isdigit(ch) && ch!='-')ch=getchar();
if(ch=='-')flag=-1,ch=getchar();
while(isdigit(ch))x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*flag;
}
inline int lowbit(int x){
return x&(-x);
}
inline unsigned int Query(int pos){
unsigned int ans=0;
while(pos){
ans+=bit[pos];
pos-=lowbit(pos);
}
return ans;
}
inline void Modify(int pos,unsigned int val){
int n=maxn-5;
while(pos<=n){
bit[pos]+=val;
pos+=lowbit(pos);
}
}
inline void initialize(int n){
int i,j,cnt=0;
mu[1]=1;vis[1]=1;
for(i=2;i<=n;i++){
if(!vis[i]){
prime[++cnt]=i;
mu[i]=-1;
}
for(j=1;j<=cnt && i*prime[j]<=n;j++){
mu[i*prime[j]]=-mu[i];
vis[i*prime[j]]=1;
if(i%prime[j]==0){
mu[i*prime[j]]=0;
break;
}
}
}
}
int main(){
int i,j,k,m,n,T,a;
#ifndef ONLINE_JUDGE
freopen("BZOJ3529.in","r",stdin);
freopen("BZOJ3529.out","w",stdout);
#endif
initialize(maxn-5);
for(i=1;i<=maxn-5;i++)
for(j=i;j<=maxn-5;j+=i)
sum[j]+=i;
for(i=1;i<=maxn-5;i++)p[i]=i;
sort(p+1,p+maxn-5+1,compr);
T=read();
int cnt=0;
while(T--){
n=read();m=read();a=read();
query[++cnt]=(node){n,m,a,cnt};
}
sort(query+1,query+cnt+1,cmp);
int pos=1;
for(i=1;i<=cnt;i++){
unsigned int ans=0;
for(;(int)sum[p[pos]]<=query[i].a;pos++)
for(j=1;j*(int)p[pos]<=maxn-5;j++)
Modify(j*p[pos],sum[p[pos]]*mu[j]);
if(query[i].n>query[i].m)swap(query[i].n,query[i].m);
unsigned int lans=0;
for(j=1;j<=query[i].n;j++){
k=min(query[i].n/(query[i].n/j),query[i].m/(query[i].m/j));
unsigned int curans=Query(k);
ans+=(curans-lans)*(query[i].n/j)*(query[i].m/j);
lans=curans;
j=k;
}
Ans[query[i].id]=ans;
}
for(i=1;i<=cnt;i++)
printf("%lld\n",Ans[i]%(1ll<<31ll));
return 0;
}