记$E(x_0, y_0)$为运用欧几里德法（辗转相除法）计算$x_0, y_0$的最大公约数的步数。即按 $$x_n=y_{n-1},\quad y_n=x_{n-1} \bmod y_{n-1},$$ 迭代计算中使$y_n=0$的$n$。可以验证$E(1,1)=1, E(10,6)=3, E(6,10)=4$。

记$S(N)=\sum_{1\le x,y\le N}E(x,y)$的和，可以验证$S(1) = 1, S(10)=221, S(100)=39826$。

求$S(5\times 10^6)$。

本题难度:

解答

本题似乎没有太高效的解法，其主要瓶颈在于需要考察不超过N的所有数对，这已经是$O(N^2)$的数量级，辗转相除法本身收敛非常快，其计算开销相比$O(N^2)$是可以忽略的。

有网友指出可以从最后一步开始逆用辗转相除法，从而反过来生成每组数对的步数，不过这只是折叠了辗转相除的过程，它并不能减少需要考察的数对数量，却反而增加了代码本身的复杂度，是一种伪优化。

本人考察了官网解法，均为暴力法+分布式计算，即便如此，用运行效率相对较高的C++也需要数个小时才能得到结果，用Python则需要数天乃至数周，因此本题暂无法提供理想Python代码，暴力枚举本身的实现非常简单，有能力做到这一题的读者显然可以自行完成。本题的最终结果是$326624372659664$。