【NOIP模拟】Lala买面包

Description

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

Solution

方法

输入一个k，题目要求判断满足一个$x^p=k$
转换一下$log_{x}k=p$，那么就是x开p次方等于k=$x^{1\over p}$，我们发现k其实并不大，可以直接枚举。
然后判断一下就好了。

小优化

因为次数p是可以因式分解的，所有只用枚举质数为次数就好了。

注意

打c++如果用pow可能会有精度问题，我们可以在pow外面打一个round四舍五入。
注意如果x=1那么就不用管它了。

Code

#include
#include
#include
#include
#include
#define fo(i,a,b) for(i=a;i<=b;i++)
#define fod(i,a,b) for(i=a;i>=b;i--)
typedef long long ll;
using namespace std;
const int maxn=1000007;
const ll da=100000000000000;
ll i,j,k,l,t,n,m,ans,tot,o,p;
int zhi[100];
bool bz,az[maxn];
ll a[50000];
int main(){freopen("bread.in","r",stdin);freopen("bread.out","w",stdout);fo(i,2,50){if(!az[i]){zhi[++tot]=i;fo(j,2,50/i){az[i*j]=1;}    }}scanf("%lld",&n);fo(i,1,n){scanf("%lld",&k);if(k==1)continue;fo(j,1,tot){double u=round(pow(k,1.0/zhi[j]));if(round(pow(1.0*u,1.0*zhi[j]))==k){++ans;break;}  }}printf("%lld\n",ans);
}

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