题面
题解
手推一下发现最优策略是：（不会证）
-
若 (x<0)，则不断 (xgets x+1) 直到 (xgeq 0) 为止。
-
若 (x>0)，则 (xgets -dfrac{1}{x})。
-
若 (x=0)，终止。
也就是说，设开始时 (x=dfrac{a}{b}<0)（若 (x>0) 则执行 (2) 操作），其中 (a<0)，(b>0)。
用 ((a,b)) 表示 (dfrac{a}{b})，那么上述操作本质是不断将 ((a,b)xrightarrow{ ext{若干次操作1}} (b-(-a)mod b,b)xrightarrow{ ext{操作2}} (-b,b-(-a)mod b))。
为了方便，用 (xrightarrow{k}) 表示 (xrightarrow{ ext{k次操作1}})，用 (Rightarrow) 表示 (xrightarrow{ ext{操作2}})。
看上去很像辗转相除法，但时间复杂度是不对的，举个反例很容易证明： ((-1,114514)xrightarrow1 (114513,114514)Rightarrow(-114514,114513)xrightarrow1(-1,114513))。
所以暴力模拟是 (O(V)) 的（其中 (V) 为 (a,b) 值域）。
但有一种神仙优化方法：
设当前 ((-a,b))，考虑在 (0<b<a<2b) 时，显然要进行的操作是：
发现 (a'=b=a-(a-b))，(b'=-a+2b=b-(a-b))，所以新的 (a')、(b') 其实是在 (a)、(b) 的基础上各减去了 (a-b)，而且 (a'-b'=a-b) 不变。
那么如果当前 ((-a,b))，且满足 (0<b<a<2b)，我们就可以不断对 (a)、(b) 减去 (a-b) 直到当前不满足 (0<b<a<2a) 为止。列方程易解得最多减去 (leftlceildfrac{2b-a}{a-b} ight ceil) 次。所以这个过程用除法 (O(1)) 计算即可。
这种算法的时间复杂度是 (O(log V)) 的。
时间复杂度证明：（来自syh巨佬）
考虑证明 (b) 在上述综合算法下是指数级下降的。
设当前为 ((-a,b))，其中 (a,b>0)。如果 (a) 不是 (b) 的倍数的话，显然会进行如下操作：
（其中 (k) 为满足 (-a+kb>0) 的最小的 (k)，显然 (0<-a+kb<b)）
设 (a'=b)，(b'=-a+kb)，那么 (b'<a')。分两种情况讨论：
-
若 (b'leqdfrac{b}{2})，那么 (b'leqdfrac{b}{2})。
废话 -
若 (b'>dfrac{b}{2})，则 (b'>dfrac{b}{2}=dfrac{a'}{2})，即 (a'<2b')，又 (b'<a')，所以满足 (b'<a'<2b')，可以进行刚刚讲到的优化算法：
对于 ((a',b'))，不断对分母分子减去 ((a'-b')) 直到当前的 (b'') 不满足 (b''<a''<2b'') 为止。
由于我们证明过 (a''-b''=a'-b'>0)，即 (a'') 恒大于 (b'') 的，所以当上述条件不满足时，必是 (a''>2b'')。
则 (b''<dfrac{a''}{2}<dfrac{a'}{2}=dfrac{b}{2})。
所以无论如何，在每次 (O(1)) 的操作后，一定有 (b'leq dfrac{b}{2})。
所以时间复杂度为 (O(log V))。
代码如下：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline ll read()
{
ll x=0;
int f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-') f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=(x<<1ll)+(x<<3ll)+(ch^'0');
ch=getchar();
}
return x*f;
}
int t;
ll a,b,ans;
ll gcd(ll a,ll b)
{
return b?gcd(b,a%b):a;
}
int main()
{
scanf("%d",&t);
while(t--)
{
ans=0;
a=read(),b=read();
if(b<0) b=-b,a=-a;
if(a>0)
{
swap(a,b),a=-a;
ans++;
}
a=-a;
while(a)
{
if(!(a%b))
{
ans+=a/b,a=0;
continue;
}
if(b<a&&a<2ll*b)
{
ll tmp=(2ll*b-a)/(a-b);//这里应该用ceil，但我精度炸了，所以先向下取整再if判断一下
ll x=a-b;
a-=tmp*x,b-=tmp*x;
if(b<a&&a<2ll*b)
{
a-=x,b-=x;
tmp++;
}
ans+=3ll*tmp;
}
else
{
ll tmp=a/b+1;
ll t=a;
a=b,b=-t+tmp*b;
ans+=tmp+1;
}
}
printf("%lld
",ans);
}
return 0;
}
/*
5
0 1
1 1
-1 2
-2 4
-8 -5
*/