[SDOI2015]约数个数和
好像被反映跳步了。。。实际上只跳了一丢丢，还是补上算了。。。
首先知道结论：
$$\sigma_0(ij)=\sum_{x\mid i}\sum_{y\mid j}[\gcd(x,y)=1]$$
我来解释一下这个东西。
对于某一个素数 $p$ 是 $ij$ 的因子，我们的 $p$ 的次数是 $k_1+k_2+1$，其中 $k_1$ 是 $i$ 中 $p$ 的次数，$k_2$ 是 $j$ 中 $p$ 的次数。
显然我们 $p$ 的可能取值只有 $k_1+k_2+1$ 种，所以我们按如上要求正好能不重复的统计这些可能。
然后我们就可以套路推了。
$$\begin{aligned}& \sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x\mid i}\sum_{y\mid j}[\gcd(x,y)=1]
\\=& \sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{x\mid i}\sum_{y\mid j}\sum_{d\mid \gcd(x,y)}\mu(d)
\\=& \sum_{x=1}^{n}\sum_{y=1}^{m}\sum_{i=1}^{\lfloor\frac{n}{x}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{y}\rfloor}\sum_{d\mid \gcd(x,y)}\mu(d)
\\ =& \sum_{x=1}^{n}\sum_{y=1}^{m}\sum_{d\mid \gcd(x,y)}\mu(d)\lfloor\dfrac{n}{x}\rfloor\lfloor\dfrac{m}{y}\rfloor
\\ =& \sum_{d=1}^{n}\mu(d)\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{y=1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\dfrac{n}{xd}\rfloor\lfloor\dfrac{m}{yd}\rfloor
\\=& \sum_{d=1}^{n}\mu(d)\sum_{x=1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\dfrac{n}{xd}\rfloor\sum_{y=1}^{\lfloor\frac{m}{d}\rfloor}\lfloor\dfrac{m}{yd}\rfloor\end{aligned}$$
然后我们设 $f(n)=\sum_{i=1}^{n}\lfloor\dfrac{n}{i}\rfloor$，这个东西好像最优的方法就是数论分块了？
我只会 $O(\sqrt{n})$ 单次算。。。
然后就变成了：
$$\begin{aligned}=& \sum_{d=1}^{n}\mu(d)f(\lfloor\dfrac{n}{d}\rfloor)f(\lfloor\dfrac{m}{d}\rfloor)\end{aligned}$$
然后前面的 $\mu$ 的前缀和可以 $O(n)$ 线性筛。。。
虽然没有对复杂度进行什么优化，但是我还是无聊套了个杜教筛上去算 $\mu$。。。
时间复杂度 $O(n^{\frac{2}{3}}+T\sqrt{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
| #include<iostream>
#include<cstdio>
#define ll long long
using namespace std;
const ll N=5e4,M=5e3;
ll T,n,m,cnt;
ll mu[N+5],prime[N+5],smu1[N+5],smu2[N+5],sum[N+5];
bool f[N+5],vis[N+5],viss[N+5];
inline void Init() {
mu[1]=1;f[1]=1;
for(ll i=2;i<=M;i++) {
if(!f[i]) {prime[++cnt]=i;mu[i]=-1;}
for(ll j=1;j<=cnt&&i*prime[j]<=M;j++) {
f[i*prime[j]]=1;
if(i%prime[j]==0) {mu[i*prime[j]]=0;break;}
mu[i*prime[j]]=-mu[i];
}
}
for(ll i=1;i<=M;i++) smu1[i]=smu1[i-1]+mu[i];
}
inline ll Sum(ll x) {
if(viss[x]) return sum[x];viss[x]=1;
for(ll i=1,j;i<=x;i=j+1) {j=x/(x/i);sum[x]+=(j-i+1)*(x/i);}
return sum[x];
}
inline ll Smu(ll x) {
if(x<=M) return smu1[x];ll tmp=x;
if(vis[tmp]) return smu2[tmp];
vis[tmp]=1;smu2[tmp]=1;
for(ll i=2,j;i<=x;i=j+1) {
j=x/(x/i);smu2[tmp]-=(j-i+1)*Smu(x/i);
}
return smu2[tmp];
}
inline ll read() {
ll ret=0,f=1;char ch=getchar();
while(ch<48||ch>57) {if(ch==45) f=-f;ch=getchar();}
while(ch>=48&&ch<=57) {ret=(ret<<3)+(ret<<1)+ch-48;ch=getchar();}
return ret*f;
}
inline void write(ll x) {
static char buf[22];static ll len=-1;
if(x>=0) {do{buf[++len]=x%10+48;x/=10;}while(x);}
else {putchar(45);do{buf[++len]=-(x%10)+48;x/=10;}while(x);}
while(len>=0) putchar(buf[len--]);
}
inline void writeln(ll x) {write(x);putchar(10);}
int main() {
T=read();Init();
while(T--) {
n=read();m=read();if(n<m) swap(n,m);
ll ans=0;
for(ll i=1,j;i<=m;i=j+1) {
j=min(n/(n/i),m/(m/i));
ans+=(Smu(j)-Smu(i-1))*Sum(n/i)*Sum(m/i);
}
writeln(ans);
}
return 0;
}
|