Codeforces Round #471 (Div. 2) C. Sad powers

本文主要是介绍Codeforces Round #471 (Div. 2) C. Sad powers，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

题意：问区间[L, R]中有多少数字可以写成的形式；

思路：：当p>=3时，x<=1e6；只有p=2时x能达到1e9；但是[L, R]区间中满足的数有(int)sqrt(R)-(int)sqrt(L-1)个，所以对于区间[L, R]先找出p>=3的情况，再加上(int)sqrt(R)-(int)sqrt(L-1)，而对于p>=3的情况打表找出来就可以了，然后排序，二分查找；

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> vec;
ll power(int j, int i){ll ret=1LL;while(i){ret*=(ll)j;if(ret>2e18||ret<0) return ret;i--;}return ret;
}
void init(){for(int i=3; i<=64; i++){int j;for( j=2; ; j++){ll temp=power(j, i);if(temp>2e18||temp<0) break;ll x=(ll)sqrt(temp);if(x*x==temp) continue;vec.push_back(temp);}}sort(vec.begin(), vec.end());unique(vec.begin(), vec.end())-vec.begin();
}
int main(){init();int Q;scanf("%d", &Q);while(Q--){ll L, R;scanf("%lld%lld", &L, &R);ll ans=upper_bound(vec.begin(), vec.end(), R)-lower_bound(vec.begin(), vec.end(), L);ans+=(ll)sqrt(R)-(ll)sqrt(L-1);printf("%lld\n", ans);}return 0;
}

 

这篇关于Codeforces Round #471 (Div. 2) C. Sad powers的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---