结论假了.
Flu:观察到f(x)不会大于3*x(Flu并不会证明).
然后考虑取等的情况,发现是有规律的:对所有取等的地方做差,得到一个最大数和很多小数,发现最大数数列之间的关系是最大数乘2加上一堆小数,而且1e6以内的小数大小不会超过1e5.于是可以通过倍增的方法求出最靠近1e15的取等的数字,剩下的暴算过去.
然而,因为最大数数列是倍增的,最靠近1e15的是8e14,意味着Flu只是把1e15的nlog优化成1.2e14的nlog,还是T飞.
查阅网上的题解说是:发现 $\gcd$ 不等于1的实际上很少,于是对一个 ${i,g}$ 考虑下一个gcd不等于1的设为 ${i+k,pre(g+k-1)}$ ,中间的gcd都是1.我们有 $\gcd(g+k-1,i+k)>1$ ,根据gcd性质相减有 $\gcd(g-i-1,i+k)>1$ 然后发现前面是常数,于是质因数分解之后对k求最小值,跳转过去即可,复杂度未知总之是能过.