[AGC015F] Kenus the Ancient Greek

oisdoaiu · 2021-04-26 16:41:59 · 题解

tag:数论，构造(?)

题意

给定 X,Y，设 g(x,y) 为 对 x,y 用辗转相除法求gcd需要的步数。求 gcd(x,y),\ x\le X,\ y\le Y 的最大值，和能取到最大值的 (x,y) 的对数。

题解

最大值很好求，考虑倒推，就是让每一步的两个数尽量小，所以让“辗转相除法”变为“辗转相减”就行了。(0,1)\to(1,2)\to(2,3)\to(3,5)，发现这个就是斐波那契数列，所以找到最大的 i,\ fib(i)\le X, fib(i+1)\le Y 就行了。

考虑求对数。由于 g(a,b)=g(a,b+ka)，所以不用考虑完所有情况，只需要考虑 g(a,b)=ans,\ a<b<2a，然后可以直接用除法计算出贡献。

接下来考虑如何找出这些 (a,b)。

把倒推过程画出来。

对于 ans=3 的情况，只有 (2,3)(3,4)，倒推路径分别为：

对于 ans=4 的情况，首先可以在 ans=3 的基础上往后扩展为 0\to1\to2\to3\to5 和 0\to1\to3\to4\to7。其次，我们还可以把第一条路径的 “3” 改大一点点，形成一条新的倒推路径：

但是只能延伸出一条新的路径，因为把第一条路径的 “3” 改为 “7” 后，

此时答案（指 \max\{g(a,b)\}）就为 5 了。因为既然 (7,9) 存在，那么 (5,8)（对应路径 0\to1\to2\to3\to5\to8） 也存在。

所以推出 ans=4 时有 (3,5)(4,7)(5,7)。

那么这个规律能否拓展到一般情况呢？考虑从 ans=k 推出 ans=k+1。

首先对于每对 ans=k 的 (a,b)，显然可以推出一对 ans=k+1 的 (b,a+b)。

然后类似于上面，考虑将最小的那条路径的结尾改大一点点，延伸出一条分支。比如 ans=k 时，第一条路径最后部分为:

那么把 b 改为 a+b，可以延伸出一条 ans=k+1 的倒推路径：

这样会让值域扩充到 (a+b,2a+b)，所以我们还要考虑 \max\{g(x,y)\} 会不会变大。实际上只用考虑最小的那条倒推路径，他的下一个元素是 a+2b，而2a+b<a+2b。也就是说这条路径的加入，不会导致第一条路径变长，即不会让 ans 变大。

那如果将最小的那条路径结尾再改大一点点呢，如果把 b 改为 2a+b，延伸出另一条路径：

此时值域被扩充到了 (2a+b,3a+b)，而由于第一条路径就是斐波那契数列，所以有 b<2a，所以 3a+b>a+2b。也就是说如果这条路径加入了，那么第一条路径还可以加入一个元素，即 \max\{g(x,y)\} 会变大，所以这条路径是不合法的。

而对于 \max\{g(x,y)\}=k 的其他倒推路径，就更不可能延伸出新的路径了（证明类似）。

所以 ans=k 时相对于 ans=k-1 时，只会多出一对 (fib(k+1),fib(k+1)+fib(k-1))

所以得到构造方法：

• ans=1$，有 $(1,2)
• ans=k$ 时对于每个 $(a,b)$，都对应 $ans=k+1$ 时的一个 $(b,a+b)
• 同时 ans=k 还会多出一对 (fib(k+1),\ fib(k+1)+fib(k-1))

  fib[0] = fib[1] = 1;
  for(register int i=2; fib[i-1]<=1e18; i++) fib[i] = fib[i-1]+fib[i-2];
  ans[1][1] = pii(1,2);
  for(register int i=2; fib[i]<=1e18; i++){
  for(register int j=1; j<i; j++) 
      ans[i][j] = pii(ans[i-1][j].second,ans[i-1][j].first+ans[i-1][j].second);
  ans[i][i] = pii(fib[i+1],fib[i+1]+fib[i-1]);
  }

然后求解对数就枚举每一对元素直接计算即可。

while(ans[res+1][1].first<=x and ans[res+1][1].second<=y) res++;
for(register int i=1; i<=res; i++){
    if(ans[res][i].first<=x and ans[res][i].second<=y) sum += (y-ans[res][i].second)/ans[res][i].first+1;
    if(ans[res][i].second<=x) sum += (x-ans[res][i].second)/ans[res][i].first+1;
    sum %= MOD;
}

注意特判一下 ans=1 时，每一对 (i,i) 都是合法的，所以加上 min(X,Y)

完整代码