CF1995C Squaring 题解

思路详解：

请注意，本题解用到了非整数计算，也就是说性能可能不如整数运算，但是易于实现，追求最优解的大佬不建议观看本题解。

这个题看似简单，但是由于涉及到了平方操作，不用高精度根本存不下，然后如果你要用高精度的话又会 T L E TLE TLE 而且巨难写。

尝试使用对数科技，根据高中数学的知识我们可以知道 log ⁡ ( n ∗ n ) = 2 × log ⁡ n \log(n* n) = 2 \times \log n log(n∗n)=2×logn，但是注意到 n ≤ 2 × 1 0 5 n \le 2 \times 10^5 n≤2×105，所以就算将平方操作转化成了 × 2 \times 2 ×2 操作仍然无法通过本题。

然后做这道题的时候笔者想到这里就觉得这道题不可做，然后果断放弃了。。

但事实上，对数科技并不是只能使用一次，我们可以通过对数的转化将 × 2 \times 2 ×2 转化成 + 2 + 2 +2，即 log ⁡ ( n × 2 ) = log ⁡ n + log ⁡ 2 \log (n \times 2) = \log n + \log 2 log(n×2)=logn+log2，因此，我们就根据上述两个等式成功将平方操作转化成了 + 2 + 2 +2​ 操作。

然后就做完了。

tip: 由于使用了非整数的运算，所以判断是否等于 0 的时候建议和 eps 作比较，防止出现精度上的问题，即出现了误差。