「SDOI 2015」约数个数和

Description

题目链接:BZOJ 3994

求如下式子的值:

本题 $T$ 组数据。

数据范围:$1\le T,n,m\le 5\times 10^4$


Solution

首先给出一个公式:

因此所求为

改变求和顺序,先枚举因数 $x$ 和 $y$

将 $x,y$ 换成 $i,j$ 吧 QAQ

开始莫比乌斯反演!设

则有

我们把 $x$ 提出就可以消除 $\gcd$ 的影响

再根据 $f(x)$ 的定义,得到答案为 $f(1)$

又因为

接下来再考虑如何求 $g(x)$,我们可以先计算 $s(x)=\sum_{i=1}^{x} \left\lfloor\frac{x}{i}\right\rfloor$,就可以 $O(1)$ 计算 $g(x)$。

时间复杂度:$O(T\sqrt{n})$


Code

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
#include <cstdio>
#include <algorithm>
const int N=5e4+5;
int tot,mu[N],p[N];
long long s[N];
bool flg[N];

void init() {
mu[1]=1;
for(int i=2;i<=5e4;++i) {
if(!flg[i]) p[++tot]=i,mu[i]=-1;
for(int j=1;j<=tot&&i*p[j]<=5e4;++j) {
flg[i*p[j]]=1;
if(i%p[j]==0) {
mu[i*p[j]]=0;
break;
} else {
mu[i*p[j]]=-mu[i];
}
}
}
for(int i=1;i<=5e4;++i) mu[i]+=mu[i-1];
for(int x=1;x<=5e4;++x) {
long long res=0;
for(int i=1,j;i<=x;i=j+1) j=x/(x/i),res+=1LL*(j-i+1)*(x/i);
s[x]=res;
}
}
int main() {
init();
int T;
for(scanf("%d",&T);T--;) {
int n,m;
scanf("%d%d",&n,&m);
if(n>m) n^=m^=n^=m;
long long ans=0;
for(int i=1,j;i<=n;i=j+1) {
j=std::min(n/(n/i),m/(m/i));
ans+=1LL*(mu[j]-mu[i-1])*s[n/i]*s[m/i];
}
printf("%lld\n",ans);
}
return 0;
}

Extended

如何证明 Solution 中的公式?

我们考虑把每个因子一一映射。

如果 $ij$ 的因子 $k$ 中有一个因子 $p^c$,$i$ 中有因子 $p^a$,$j$ 中有因子 $p^b$。我们规定:

  • 如果 $c\le a$,那么在 $i$ 中选择。
  • 如果 $c>a$,那么我们把 $c$ 减去 $a$,在 $j$ 中选择 $p^{c-a}$(在 $j$ 中选择 $p^e$ 表示的是 $p^{a+e}$)

对于 $ij$ 的因子 $k$ 的其他因子同理。于是对于任何一个 $k$ 有一个唯一的映射,且每一个选择对应着唯一的 $k$。

通过如上过程,我们发现:对于 $ij$ 的因子 $k=\prod {p_i}^{c_i}$,我们不可能同时在 $i$ 和 $j$ 中选择 $p_i$(优先在 $i$ 中选择,如果不够就只在 $j$ 中选择不够的指数),故 $x$ 和 $y$ 必须互质。

等式得证。

0%