[题解] [USACO23OPEN] Good Bitstrings P

· · 题解

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;
}