2020.08.04【NOIP提高组】模拟：Lala买面包 总结

2020.08.04【NOIP提高组】模拟：Lala买面包 总结

Description

众所周知，lala是一名非常喜欢看天线宝宝拉拉吃面包的高中生，在经过无数次的重播那堪称经典的画面之后，lala终于感到看不下去了，决定自己也去吃回面包。
于是lala来到了一家面包店，但由于这家面包店的面包实在太多了，lala难以选择该买哪些面包，但这自然难不倒机智的lala，他先给每种面包定了一个美味度，并只购买美味度能表示成 x p x^p xp($x$，$p$均为大于等于2的正整数)的面包，但即便如此，lala还是难以快速地知道该买哪些面包，会买多少面包，你能帮帮他吗？

Input

第一行一个整数$N$，表示面包店里的面包总数。
第二行$N$个正整数 w i w_i wi​，表示这$N$个面包的美味度。

Output

一个整数，表示lala总共会买的面包数。

Sample Input

4
7 8 9 10

Sample Output

2

Data Constraint

对于$10\%$的数据，$1\le N\le 10$。
对于$100\%$的数据， 1 ≤ N ≤ 1 0 6 ， w i ≤ 1 0 14 1\leq N\leq 10^6 ，w_i\leq 10^{14} 1≤N≤106，wi​≤1014 。

总结

比赛思路： 暴力预处理（类似正解），拿了80分。
正解： 暴力预处理+玄学优化，将可行的数放入数组里面，接着排序二分答案。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！