网站导航页设计,网站建设与管理综合实训,企业查找,wordpress 加入引导页思路详解#xff1a;
请注意#xff0c;本题解用到了非整数计算#xff0c;也就是说性能可能不如整数运算#xff0c;但是易于实现#xff0c;追求最优解的大佬不建议观看本题解。 这个题看似简单#xff0c;但是由于涉及到了平方操作#xff0c;不用高精度根本存不下
请注意本题解用到了非整数计算也就是说性能可能不如整数运算但是易于实现追求最优解的大佬不建议观看本题解。 这个题看似简单但是由于涉及到了平方操作不用高精度根本存不下然后如果你要用高精度的话又会 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)lognlog2因此我们就根据上述两个等式成功将平方操作转化成了 2 2 2 操作。
然后就做完了。
tip: 由于使用了非整数的运算所以判断是否等于 0 的时候建议和 eps 作比较防止出现精度上的问题即出现了误差。
