【NOIP2015模拟11.2晚】Lala买面包题解

Description

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

Input

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

Output

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

Sample Input

4
7 8 9 10

Sample Output

2

Data Constraint

对于10%的数据，1 <=N <=10。
对于100%的数据，1<= N<=10^6 ，wi<=10^14 。

Solution

发现指数比较小，只有47，便可以枚举指数，然后二分一个底数，判断时用快速幂优化即可。还有一个比较重要的优化，每一次二分的$l$和$r$, l = 2 , r = l 1 l=2,r=l_{1} l=2,r=l1​， l 1 l_{1} l1​指的是上一次二分出来的答案。有点难调，好好打。

Code

#include
#include
#define ll long long
using namespace std;
ll n,ans;
ll power(ll x,ll y) {ll result=1;while(y) {if(y&1)result*=x;//if(result<0||result>1e14)return 1e15;x*=x;//if(x<0||x>1e14)return 1e15;y>>=1;}return result;
}
int main() {freopen("bread.in","r",stdin);freopen("bread.out","w",stdout);scanf("%lld",&n);for(register ll i=1;i<=n;i++) {ll x,l=2,r;scanf("%lld",&x);r=sqrt(x);for(register ll j=2;j<=50;j++) {while(l<=r) {ll mid=(l+r)>>1;ll pow=power(mid,j);if(pow<=0||pow>x)r=mid-1;else if(pow<x)l=mid+1;else if(pow==x) {l=mid;break;}}if(power(l,j)==x) {ans++;break;}r=l;l=2;}}printf("%lld",ans);fclose(stdin);fclose(stdout);return 0;
}

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