自动搬运

查看原文

来自洛谷，原作者为

	C1942huangjiaxu 我将终究顺流入大海

搬运于2025-08-24 23:01:15，当前版本为作者最后更新于2024-07-26 22:01:58，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

2024.8.23 upd: 修复了参考代码中 $n\lt b$ 时出错的问题。

本题解主要讲述官方题解怎么实现。

首先可以发现，每个分数都可以由 $2$ 开始，若干 $+2$，取倒数，这样的若干次操作得到，并且每个分数操作序列唯一。

这里不妨假设 $n\le m$，我们只考虑 $\lt 1$ 的分数。

那么每次操作，相当于，加上一个偶数 $u$，然后取倒数。

也就是官方题解中连分数的形式：

$$\cfrac{1}{u_1+\cfrac{1}{u_2+\cfrac{1}{u_3+\cfrac{1}{u_4+\cdots}}}} $$

假设当前的值为 $\cfrac a b$，那么加上 $u$ 后取倒数，就是 $\cfrac {b}{bu+a}$。

我们搜索中，把 $u$ 中的最大值设为 $x$，统计答案时直接统计所有可能的 $x$，官方题解中说明，这样的搜索量是可以接受的。

于是，我们的搜索过程就可以描述为，先进行若干次操作，得到分数 $\cfrac{a}{b}$，然后加入最大值 $x$，搜索分数 $\cfrac {ax+b}{cx+d}$，同时我们要维护最大值 $x$ 的下界来统计答案。

将不可能成为答案的状态剪枝，最后大概统计 $4\times 10^8$ 次答案。

参考代码：

#include<bits/stdc++.h>
using namespace std;
int n,m;
long long ans;
void dfs1(int a,int b,int c,int d,int v){
	if(1ll*a*v+b>n)return;
	ans+=max(0,min(!a?m:(n-b)/a,(m-d)/c)-v+1)+max(0,(n-d)/c-v+1);
	for(int u=1;;++u){
		int A=2*c*u+a,B=2*d*u+b;
		if(1ll*A*max(v,u+1)+B>m)break;
		dfs1(c,d,A,B,max(v,u+1));
	}
}
void dfs2(int a,int b,int v){
	for(int u=1;;++u){
		int c=2*u*b+a;
		if(2ll*c*max(v,u)+b>m)break;
		dfs2(b,c,max(v,u));
	}
	dfs1(0,b,2*b,a,v);
}
int main(){
	scanf("%d%d",&n,&m);
	if(n>m)swap(n,m);
	dfs2(0,1,1);
	printf("%lld\n",ans);
	return 0;
}