自动搬运

查看原文

来自洛谷，原作者为

	Prean 不断倒下，不断站起来，不停地与自己作斗争

搬运于2025-08-24 22:33:37，当前版本为作者最后更新于2021-08-23 18:18:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题意：给定 $n$，求方程 $\frac 1 a - \frac 1 b=\frac 1 n$ 的所有解，且解必须满足 $\gcd(a,b,n)=1$。

以下内容搬运自官方题解：

转化一下：

$$bn=a(b+n)$$ $$a=\frac {bn} {b+n}$$

根据 $\gcd(a,b,n)=1$，有：

$$\gcd(\frac {bn} {b+n},b,n)=\gcd(\frac {bn} {b+n},\gcd(b,n))=1 $$

接下来设 $b=x \times \gcd(b,n),n=y \times \gcd(b,n)$，那么一定有 $\gcd(x,y)=1$。

于是：

$$\gcd(\frac {xy} {x+y} \times \gcd(b,n),\gcd(b,n))=1 $$$$\gcd(b,n)|(x+y)$$

而 $\gcd(xy,x+y)=1,\frac {xy} {x+y} \times \gcd(b,n)$ 是整数，所以有 $(x+y)|\gcd(b,n)$。

于是 $ x+y=\gcd(b,n),b+n=\gcd(b,n) \times (x+y) = \gcd(b,n)^2 $。

相当于求方程 $x+n=\gcd(x,n)$。（这里的 $x$ 在上面是 $b$）

下面为了方便，设 $\gcd(x,n)=d,c=dk$。

$$d^2=dk+x$$ $$x=d \times (d-k)$$

然后对于 $d$，枚举可行的 $k$，最后检查一下是否合法就行。

检查是否合法的瓶颈在于，计算 $ \gcd(x,c)=\gcd(d(d-k),c)=\gcd(d(d-k),dk)=d \times \gcd(d-k,k) $。

这里的 $d-k$ 和 $k$ 一定有一个数不大于 $\sqrt n$，所以根据 $\gcd(a,b)=\gcd(a \bmod b,b)$，可以直接预处理一个 $\sqrt n \times \sqrt n$ 的表。

再往下推，发现实际上是判断 $d \times \gcd(d-k,k)=d$，也就是判断 $d$ 和 $k$ 是否互质，所以打表可以使用一个 bool 类型的数组来降低常数。

到这里，复杂度已经变成 $O(n\log n+T)$ 的了。在加强版中，这个做法只跑了 1s，并且卡掉了 $O(n+T\sqrt n)$ 的暴力，还在原版跑到了300ms。

#include<cstdio>
#include<vector>
typedef unsigned uint;
typedef unsigned long long ull;
const uint M=2e6;
uint T,mx,n[100005],ans1[M+5];bool _check[1420][1420];
ull ans[M+5],ans2[M+5];
inline ull min(const ull&a,const ull&b){
	return a>b?b:a;
}
signed main(){
	register uint i,j,x;
	scanf("%u",&T);_check[0][1]=true;
	for(i=1;i<=1415;++i)_check[1][i]=true;
	for(i=2;i<=1415;++i){
		for(x=0,j=i;j<=1415;++j){
			_check[i][j]=_check[x][i];
			if(++x==i)x=0;
		}
	}
	for(i=1;i<=T;++i)scanf("%u",n+i),mx=n[i]>mx?n[i]:mx;
	for(i=1;i<=mx;++i)ans2[i]=0x7f7f7f7f7f7f7f7f;
	for(i=1;i<=mx;++i){
		for(j=1,x=i;j<=i&&x<=mx;++j,x+=i){
			if(_check[i%j][j])ans2[x]=min(ans2[x],1ull*i*(i-j)),++ans1[x];
		}
	}
	for(ans1[i=1]=0;i<=mx;++i)ans1[i]+=ans1[i-1];
	for(i=1;i<=T;++i)printf(n[i]==1?"0\n":"%u %llu\n",ans1[n[i]],ans2[n[i]]);
}