小浩的幂次运算(快速幂)
传送门
看到该题庞大的数据量以及幂运算,很明显,我们需要使用快速幂解决
然后对于该,我们可以对两边同时取对数,这样就可以得到对应的指数是多少,这里可以利用cmath库函数log()进行对数计算,只需进行简单的对数转换即可,例如log(8)/log(2)=log2(8)=3
值得注意的是因为这里利用了除法,因此还需要注意分母为0的情况
#include<iostream> #include<cmath> #define LL long long//开long long using namespace std; LL fun(LL a,LL b){//快速幂模板 LL ans=1,temp,base,index; temp=a; base=a; index=b; while(b>0){ if(b&1){ ans=ans*temp; } temp=temp*temp; b>>=1; } // cout<<base<<"^"<<index<<"="<<ans<<endl; return ans; } signed main(){ LL L,R,W,i=0,count=0; cin>>L>>R>>W; if(W==1){//特判分母为0的情况(因为log(1)=0) if(1>=L&&1<=R){ cout<<1<<endl; }else{ cout<<-1<<endl; } return 0; } LL index1=log(L)/log(W);//对数转换 LL index2=log(R)/log(W); for(int i=index1;i<=index2;i++){ LL res=fun(W,i);//得到对应数字 if(!(res>=L&&res<=R)){//是否符合 continue; } if(count==0){ cout<<res; }else{ cout<<" "<<res; } count++; } if(count==0){//一个都没输出就输出-1 cout<<-1; } cout<<endl; return 0; }