OI - 「SDOI2014」数表(洛谷) | Lucky_Glass's Blog
0%

OI - 「SDOI2014」数表(洛谷)

当数(论)与数(据结构)搞在一起的时候


# 题面

> Linked 洛谷 P3312

点击展开/折叠 (简化)题面

给定 $N,M,a$,求

$$\sum_{i=1}^N\sum_{j=1}^N[\sigma(\gcd(i,j))\le a]\sigma(\gcd(i,j))$$

多组询问,每次给定 $N,M,a$。


# 解析

反演题总是逃不开推式子的,还是套路枚举 $\gcd$(不妨假设 $n\le m$):

然后反演

本来如果没有 $a$ 的限制($a\to\infty$),就可以直接 $O(N\sqrt N)$ 预处理 $G(t)=\sum_{d\mid t}\mu\left(\frac td\right)\sigma(d)$ 即可;但是加上限制后有一些 $\sigma(d)$ 不能对 $G(T)$ 产生贡献了,于是考虑动态维护 $G(T)$。

离线按 $a$ 从小到大处理询问,当 $a$ 增大时,就会有一些 $\sigma(d)$ 能够产生贡献了,枚举这些 $d$,$d$ 能对其倍数 $T$ 的 $G(T)$ 产生贡献。直接枚举 $T$,因为 $d$ 恰好会有 $1\sim N$ 的取值,则枚举 $T$ 的均摊复杂度是 $O(N\log N)$。

考虑到数论分块时要用到 $G(T)$ 的区间和,则单点修改区间求和可以用常数相对较小的树状数组。

这样每次询问要数论分块加上树状数组,复杂度 $O(Q\log N\sqrt N)$,而总共 $N$ 次修改贡献,均摊后每次 $O(\log^2 N)$,则修改复杂度 $O(N\log^2 N)$,总复杂度 $O(Q\log N\sqrt N+N\log^2 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
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int Q=2e4+10,N=1e5+10;
const unsigned MOD=(unsigned)2147483648;
#define ci const int &
#define lowbit(x) ((x)&((-x)))

bool vis[N];
int cas,nprm,qry[Q][3],qid[Q],prm[N];
unsigned tre[N],mu[N],ans[Q];
pair<unsigned,int> sig[N];

inline int Read(){
register int r=0,c=getchar();
while(c<'0' || '9'<c) c=getchar();
while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar();
return r;
}
bool cmp(ci a,ci b){return qry[a][2]<qry[b][2];}
void Update(int pos,ci key){while(pos<N) tre[pos]+=key,pos+=lowbit(pos);}
unsigned Query(int pos){unsigned ret=0;while(pos) ret+=tre[pos],pos-=lowbit(pos);return ret;}
void Init(){
for(int i=1;i<N;i++){
for(int j=1;j*j<=i;j++)
if(i%j==0){
sig[i].first+=(unsigned)j;
if(j*j!=i) sig[i].first+=(unsigned)i/j;
}
sig[i].second=i;
}
sort(sig+1,sig+N);
mu[1]=1;
for(int i=2;i<N;i++){
if(!vis[i]) mu[prm[++nprm]=i]--;
for(int j=1;j<=nprm && prm[j]*i<N;j++){
vis[prm[j]*i]=true;
if(i%prm[j]==0) break;
mu[prm[j]*i]=-mu[i];
}
}
}
int main(){
Init();
cas=Read();
for(int i=1;i<=cas;i++){
qry[i][0]=Read(),qry[i][1]=Read(),qry[i][2]=Read();
qid[i]=i;
}
sort(qid+1,qid+1+cas,cmp);
for(int I=1,pos=1;I<=cas;I++){
int i=qid[I],A=qry[i][2];
while(pos<N && sig[pos].first<=(unsigned)A){
int num=sig[pos].second;
for(int j=num;j<N;j+=num)
Update(j,mu[j/num]*sig[pos].first);
pos++;
}
unsigned n=(unsigned)qry[i][0],m=(unsigned)qry[i][1];
if(n>m) swap(n,m);
for(unsigned j=1;j<=n;j++){
unsigned k=min(n/(n/j),m/(m/j));
ans[i]+=(n/j)*(m/j)*(Query(k)-Query(j-1));
j=k;
}
}
for(int i=1;i<=cas;i++) printf("%d\n",ans[i]%MOD);
return 0;
}

THE END

Thanks for reading!

> Linked 404 Not Found-Bilibili