NOI2018模拟赛(十) Problem C:gcd

题目描述

有\(Q\)组询问,每组给出\(A,B\),求\(1\le x\le A,1\le y\le B\),\(f(x,y)\)的最大值,并输出取到最大值的有序对\((x,y)\)的个数。

\(f\)的计算规则如下

1.\(f(a,b)=f(b,a),(b>a)\)

2.\(f(a,0)=0\)

3.\(f(a,b)=f(b,a\bmod b)\)

题解

题目写的这么神,那我们考虑乱搞。

首先有个常识,辗转相除在两个斐波那契数之间会取到最大次数。

然后写个暴力,把小范围内的所有有序对的答案都算出来。

题目给出了两个限制,就相当于在算出来的那个矩阵上从左上角切一个\(A\times B\)的矩形,求里面的最大值和最大值的个数,显然横竖没有影响。

那我们就可以把所有对答案可能有贡献的地方打印出来(也就是打印出以\((x,y)\)为右下角的矩形里面\((x,y)\)取到最大值的点)。

然后发现无论打印最大值为几的图,大致都和下面这个差不多。

图上大致是有几行几列的点,然后还有两个特殊的点,而且每行每列还呈现周期性变化。

那么把特殊点的坐标和每列第一个点的坐标写下来。

答案 2 3 4 5 6
special (4,3) (7,5) (11,8) (18,13) (29,21)
normal (3,2) (5,3);(7,4) (8,5);(11,7);(12,7) (13,8);(18,11);(19,11);(19,12) (21,13);(29,18);(30,19);(31,18);(31,19)

嗯,写不下了。

special的点横纵坐标竟然都是线性递推的关系,每一个答案normal的点竟然都是由上一行个答案所有的点演变而来\((x,y)\rightarrow (x+y,y)\)。

没了。

还有神奇的正解,其实最后的代码差不多。

设\(f(a,b)\)表示欧几里得步数。

我们先设斐波那契数\(F_0=1,F_1=1,F_{i+2}=F_{i+1}+F_i\)
容易发现\(f(F_k,F_{k+1})=k\)。

结论一:如果\(f(x,y)=k\),且\(y>x\),则一定有\(x\ge F_k\)以及\(y>=F_{k+1}\)。
这个可以用归纳法证明。

然后我们发现,对于\(gcd(x,y)>1\)如果\(f(x,y)>1\)这样的\((x,y)\)不会计算入答案。
这个也好证。

于是我们只需要在答案等于\(1\)的时候特判,其余情况当然只需要考虑\(\gcd\)为\(1\)的点对。

我们定义如果不存在\(x_1 < x\)和\(y_1 < y\)使得\(f(x_1,y_1) > f(x,y)\)那么\((x,y)\)是好的。
显然我们只统计好的点对。

然后我们定义如果\(f(x,y)=k\)且\(x,y\le F_{k+2}+F_{k−1}\)那么\((x,y)\)是优秀的。

结论二:如果\((x,y)\)是好的,那么一步后会变成优秀的。
可以用反证法证明。

然后我们只需要找出所有优秀的点对,就很容易统计答案。
找的方法是用\(k\)的得到\(k+1\)的。

优秀的点对有多少呢?
在最小的情况下是\((F_k,F_{k+1})\),容易发现它只会产生\(2-3\)个新的,而其余的则只能产生\(1\)个。
因此是\(log\)级别的。


在《NOI2018模拟赛(十) Problem C:gcd》上留下第一个评论