自动搬运

查看原文

来自洛谷，原作者为

	UltiMadow Well I do.

搬运于2025-08-24 22:46:12，当前版本为作者最后更新于2023-04-20 21:32:16，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

upd: 修正了一些错误（

考虑把 gen_string 的过程画到平面上，即画成一条从 $(0,0)$ 到 $(a,b)$ 的折线，折线上的所有点即可表示 gen_string 的所有前缀。

称折线上一个点合法当且仅当它所代表的的前缀合法。

下文中所有射线 $(x,y)$ 为以原点为端点，经过 $(x,y)$ 的射线。

性质 1：点 $(x,y)$ 合法当且仅当对于任意满足 $0\le x_0\le x\land 0\le y_0\le y$ 的点 $(x_0,y_0)$ 都有它在射线 $(x,y)$ 和 $(a,b)$ 同侧（在射线上的点定义为位于射线左上方）。

证明：考虑反证，假设存在点 $(x_0,y_0)$ 不在射线 $(x,y)$ 和 $(a,b)$ 同侧，不妨假设 $(x,y)\times (a,b)>0$。

取 $x_0$ 最小的满足条件的点（如果有多个则取 $y_0$ 最大的），容易证明 $(a,b)$ 的折线经过 $(x_0,y_0)$。

由于要求 $(a,b)$ 的折线和 $(x,y)$ 的折线重合，所以 $(x,y)$ 的折线也经过 $(x_0,y_0)$，而在这之后一步 $(a,b)$ 的折线会向上走，$(x,y)$ 的折线会向右走，矛盾。

性质 2：对于满足 $f_1\times f_2=1$ 的整点 $f_1,f_2$，任意满足 $f_1\times f>0\land f\times f_2>0$ 的整点 $f$ 都有 $f=k_1f_1+k_2f_2$，其中 $k_1,k_2$ 为正整数。

证明：充分性显然，下证必要性。

构造 $k_2=f_1\times f,k_1=f\times f_2$，容易证明 $f_1\times f=f_1\times(k_1f_1+k_2f_2)\land f\times f_2=(k_1f_1+k_2f_2)\times f_2$，从而 $f=(f_1\times f)f_2+(f\times f_2)f_1$，由于 $f_1,f_2,f$ 均为整点，可得 $k_1,k_2$ 均为正整数。

又一个向量分解为两个线性无关的向量的分解方式唯一，所以必要性得证。

由性质 2，可得 $f_1+f_2$ 是 $f_1$ 与 $f_2$ 之间最小的整点。

考虑如下算法：

1. 初始令 $f_1=(0,1),f_2=(1,0)$，满足 $f_1\times f_2=1$，过程中保证射线 $f_1$ 右下方及射线 $f_2$ 左上方（不含射线 $f_2$ 上的点）都被统计过了，且 $f_1$ 和 $f_2$ 均为合法点。
2. 记 $f=f_1+f_2$，则 $f$ 为合法点（由 $f$ 是 $f_1$ 与 $f_2$ 之间的最小整点保证），接下来按照 $f$ 对于 $(a,b)$ 的位置决定令 $f_1=f$ 或 $f_2=f$，继续向下递归。
3. 若 $f_2\times f=0$，则结束算法

但是这个算法漏统计了若干个形如 $kf_2$ 的点，考虑完善一下。

性质 3：若当前的 $f$ 满足 $f\times (a,b)>0$，记在此之前 $f_1$ 已经连续变化了 $k$ 次，则 $(k+2)f_2$ 合法。

证明：发现 $(k+2)f_2$ 在 $f+f_2$ 的平行四边形内，而 $f+f_2$ 为 $f$ 与 $f_2$ 之间的最小点，所以不存在横纵坐标都比 $(k+2)f_2$ 小的点满足它在 $f$ 与 $(a,b)$ 之间（这个画一下图应该会比较清楚）。

性质 4：算法结束时一定有 $f_2=(\frac a{\gcd(a,b)},\frac b{\gcd(a,b)})$ 且 $f_1\times (a,b)=\gcd(a,b)$。

证明：考虑在算法执行过程中维护 $x_1=f_1\times(a,b),x_2=(a,b)\times f_2$，则每一轮 $f_1=f$ 或 $f_2=f$ 会使 $x_1,x_2$ 中较大值减去较小值，即辗转相减，最后剩余的数即为 $\gcd(a,b)$。

由于 $f_2=k(a,b)$ 且 $f_1\times f_2=1$，可以推得 $f_2=(\frac a{\gcd(a,b)},\frac b{\gcd(a,b)})$。

不难发现算法结束时 $kf_2$ 和 $kf_2+f_1$ 均合法，所以答案还要加上 $2(\gcd(a,b)-1)$。

根据性质 4，这个算法是一个辗转相减的形式，将这个过程变为辗转相除即可做到单次询问 $\mathcal O(\log(a+b))$。

code:

#include<bits/stdc++.h>
#define int long long
using namespace std;
int T,a,b;
int solve(int a,int b){
	int f1=b,f2=a,ret=0,co=1;
	while(f2){
		if(f1>f2)ret+=co*((f1-1)/f2),f1=(f1-1)%f2+1;
		else ret+=f2/f1,f2%=f1,co=2;
	}
	return ret+2*(f1-1);
}
signed main(){
	scanf("%lld",&T);
	while(T--){
		scanf("%lld%lld",&a,&b);
		printf("%lld\n",solve(a,b));
	}
	return 0;
}