区间gcd为什么不超过nlogC种可能？

[LibroWu]

rt，C是区间最大值，n是区间长度。看到有这个结论，不知道怎么证明orz。

[Sakits]

首先，对于任意一个左端点，显然随着右端点的右移，这个区间的gcd是单调不升的。然后因为一个数的质因子的个数是logC级别的，所以确定了左端点之后，无论右端点在哪，这个区间的gcd个数都不超过logC。
一共 n 个左端点所以是 nlogC。