自动搬运

查看原文

来自洛谷，原作者为

	qwaszx 不再为往事受困.

搬运于2025-08-24 21:23:29，当前版本为作者最后更新于2019-05-09 15:57:32，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

暴力太不优雅了，来讲一种优雅的做法

有一种神奇的东西叫做Stern-Brocot树

先上图

(图片来自这里)

初始两个分数$0/1$和$1/0$，然后每次对于相邻的两个分数$m/n$和$m'/n'$，把$(m+m')/(n+n')$插入到它们中间.

可以证明它枚举了所有非负有理数.

对于任何阶段的相邻分数都有$m'n-mn'=1$，这可以通过归纳法证明.于是可以得到两个结论:

1. $gcd(n,m)=1$，根据裴蜀定理

2. $\frac{m}{n}<\frac{m+m'}{n+n'}<\frac{m'}{n'}$ 很明显

这两个性质可以保证构造出所有非负有理数，因为每往下走一层分子和分母中至少有一个会增加.

还有一点是这棵树是一个二叉搜索树

对于一个数$x$，寻找离他最近的分数只需要进行如下的操作:

int sgn(double x){return (x>eps)-(x<-eps);}
int lm=0,ln=1,rm=1,rn=0;
for(int mm=1,nn=1;mm<=m&&nn<=n;mm=lm+rm,nn=ln+rn)
{
	switch(sgn(x-1.*mm/nn))
	{
		case 0:{printf("%d/%d\n",mm,nn);return 0;}
		case 1:lm=mm,ln=nn;break;
		case -1:rm=mm,rn=nn;break;
	}
}

和二叉查找树操作差不多.

不过这样只是限定了$x$在$[lm/ln,rm/rn]$范围内，还需要判断一步才行.

实现上为了减小常数规避了除法.不过这题的数据看起来还是挺水的，优不优化一个样

复杂度$O(n)$，但实际上只有极大和极小的数会卡到这个级别，一般是$O(\log n)$左右的(斐波那契数列式增长?).

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const double eps=1e-15;
int n,m;double x;
int sgn(double x){return (x>eps)-(x<-eps);}
int main()
{
	scanf("%d%d",&m,&n);
	scanf("%lf",&x);
	int lm=0,ln=1,rm=1,rn=0;
	for(int mm=1,nn=1;mm<=m&&nn<=n;mm=lm+rm,nn=ln+rn)
	{
		switch(sgn(x*nn-mm))
		{
			case 0:{printf("%d/%d\n",mm,nn);return 0;}
			case 1:lm=mm,ln=nn;break;
			case -1:rm=mm,rn=nn;break;
		}
	}
	if(rn==0){printf("%d/%d\n",lm,ln);return 0;}
	switch(sgn((x-1.*lm/ln)-(1.*rm/rn-x)))
	{
		case 1:printf("%d/%d\n",rm,rn);break;
		case 0:puts("TOO MANY");break;
		case -1:printf("%d/%d\n",lm,ln);
	}
}

猜测$rank1$也是写的这个东西并且新评测姬跑得略慢(