中国国家集训队互测 2012,by ayq,一道 数论 题。
题目链接:Luogu P4466。
题目
一句话题意。
给定 \(n(n\leq 2^{31}-1)\),求满足
- \[1\leq a<b\leq n\]
- \[(a+b)\mid ab\]
的数对 \((a,b)\) 的个数。
题解
思路
第一个条件没得说,主要从第二个条件 \((a+b)\mid(a\times b)\) 入手。
考虑恒等式 \(\gcd(a,b)=\gcd(a-b,b)\),我们不难发现
\[\gcd(a,b)=\gcd(a+b,a)\]
进一步地,我们有
\[
\begin{aligned}
&\gcd(a,b)=1\\
\Rightarrow&\gcd(a+b,a)=\gcd(a+b,b)=1\\
\Rightarrow&(a+b)\nmid ab
\end{aligned}
\]
不妨设 \(d=\gcd(a,b),a=id,b=jd\),那么我们有
\[
(id+jd)\mid ijd^2 \Rightarrow (i+j)\mid ijd
\]
又 \(\gcd(i,j)=1\Rightarrow (i+j)\nmid ij\),所以有
\[(i+j)\mid d\]
经过上面的推理,我们不难写出答案的表达式
\[
\texttt{ans}=\sum _ d\sum^{\left\lfloor\frac{n}{d}\right\rfloor} _ {i=1}\sum^{i-1} _ {j=1}\left[(i+j)\mid d][\gcd(i,j)=1\right]
\]
改变求和顺序
\[
\texttt{ans}=\sum^n _ {i=1}\sum^{i-1} _ {j=1}\left[\gcd(i,j)=1\right]\sum _ d\left[(i+j)\mid d\right]
\]
显然 \(d\in [1,\left\lfloor\frac{n}{i}\right\rfloor]\),所以我们有
\[\left(\sum _ d[(i+j)\mid d]\right)\Rightarrow \left\lfloor\frac{\left\lfloor\frac{n}{i}\right\rfloor}{i+j}\right\rfloor\]
\[
\texttt{ans}=\sum^n _ {i=1}\sum^{i-1} _ {j=1}[\gcd(i,j)=1]\left\lfloor\frac{\left\lfloor\frac{n}{i}\right\rfloor}{i+j}\right\rfloor
\]
先开一下括号
\[
\texttt{ans}=\sum^n _ {i=1}\sum^{i-1} _ {j=1}[\gcd(i,j)=1]\left\lfloor\frac{n}{i(i+j)}\right\rfloor
\]
观察到当 \(i>\sqrt{n}\) 时 \(\left\lfloor\frac{n}{i(i+j)}\right\rfloor=0\),我们可以缩小 \(i\) 的范围。
\[
\texttt{ans}=\sum^\sqrt{n} _ {i=1}\sum^{i-1} _ {j=1}\left\lfloor\frac{n}{i(i+j)}\right\rfloor[\gcd(i,j)=1]
\]
考虑到 \(\texttt{Dirichlet}\) 卷积中 \((\mu\ast 1)(x)=\epsilon(x)\),即莫比乌斯反演。
所以我们可以进一步化简答案。
\[
\texttt{ans}=\sum^\sqrt{n} _ {i=1}\sum^{i-1} _ {j=1}\left\lfloor\frac{n}{i(i+j)}\right\rfloor\sum _ {k\mid\gcd(i,j)}\mu(k)
\]
设 \(i=xk,j=yk\),交换求和顺序,有
\[
\texttt{ans}=\sum^\sqrt{n} _ {k=1}\mu(k)\sum^{\left\lfloor\frac{\sqrt{n}}{k}\right\rfloor} _ {i=1}\sum^{i-1} _ {j=1}\left\lfloor\frac{n}{xk(xk+yk)}\right\rfloor
\]
最后化简为
\[
\texttt{ans}=\sum^\sqrt{n} _ {k=1}\mu(k)\sum^{\left\lfloor\frac{\sqrt{n}}{k}\right\rfloor} _ {i=1}\sum^{i-1} _ {j=1}\left\lfloor\frac{\left\lfloor\frac{n}{xk^2}\right\rfloor}{x+y}\right\rfloor
\]
最后分析时间复杂度,发现 \(\zeta(1.5)\in\left[2.6,2.7\right]\),所以时间复杂度为 \(\Theta(n^{\frac{3}{4}})\)。
代码
#include<bits/stdc++.h> using namespace std; #define reg register typedef long long ll; const int MAXSIZE=1e5+5; bitset<MAXSIZE> vis; int tot,prime[MAXSIZE]; int mu[MAXSIZE]; inline void Init(reg int n){ mu[1]=1; for(reg int i=2;i<=n;++i){ if(!vis[i]){ mu[i]=-1; prime[++tot]=i; } for(reg int j=1;j<=tot&&i*prime[j]<=n;++j){ vis[i*prime[j]]=true; if(i%prime[j]==0) break; mu[i*prime[j]]=-mu[i]; } } return; } inline ll calc(reg int x,reg int y){ reg ll res=0; reg int z=x<<1; if(!y) return 0; for(reg int i=x+1;i<z;i=x+1){ if(!(y/i)) return res; x=min(y/(y/i),z-1); res+=(x-i+1)*(y/i); } return res; } int n; int main(void){ Init(1e5); scanf("%d",&n); reg int m=sqrt(n); reg ll ans=0; for(reg int i=1;i<=m;++i){ if(!mu[i]) continue; reg ll sum=0; for(reg int j=1;j*i<=m;++j) sum+=calc(j,n/(i*i*j)); ans+=sum*mu[i]; } printf("%lld\n",ans); return 0; }
近期评论