题解 CF955C 【Sad powers】
VenusM1nT
2020-11-20 20:41:47
先考虑 $\leq n$ 有多少个满足的,考虑 $p=2$ 的情况,显然对于 $n$,有 $\lfloor \sqrt{n}\rfloor$ 个满足条件的。然后考虑 $p>2$,若 $p=3$,有 $\lfloor \sqrt[3]{n} \rfloor$ 种,但这两种情况必然有重复的,比如 $64$,$p>3$ 同理,因此考虑对于 $p>2$ 单独计算。注意到 $\sqrt[3]{10^{18}}=10^6$,因此可以考虑对于 $x\in[2,10^6]$,$3\leq p\leq 59$,将**不为平方数**的 $x^p$ 加到一个 vector 里面,排序去重之后,只需要二分出 $n$ 在 vector 中的位置就可以得到 $p>2$ 时满足条件的。最后搞个容斥就出来了。
![](https://t1.picb.cc/uploads/2020/10/26/tYMToc.png)
```cpp
#include<bits/stdc++.h>
#define N 100
#define reg register
#define inl inline
#define int long long
#define inf 1e18
using namespace std;
int Q;
vector <int> g;
inl int Pow(reg int x,reg int y)
{
reg int res=1;
for(;y;y>>=1,x=x*x) if(y&1) res=res*x;
return res;
}
inl void Init()
{
for(reg int i=3;i<=59;i+=2)
{
for(reg int j=1;j<=1000000;j++)
{
reg int cnt=Pow(j,i);
if(!cnt || cnt==1 || (int)sqrt(cnt)*(int)sqrt(cnt)==cnt) continue;
if(cnt>inf || cnt<0) break;
g.push_back(cnt);
}
}
sort(g.begin(),g.end());
g.erase(unique(g.begin(),g.end()),g.end());
}
inl int Calc(reg int n)
{
reg int res=(int)sqrt(n);
reg int pos=lower_bound(g.begin(),g.end(),n)-g.begin();
if(pos<(int)g.size() && g[pos]>n) pos--;
else if(pos==(int)g.size()) pos--;
res+=pos;
return res;
}
signed main()
{
Init();
scanf("%lld",&Q);
while(Q--)
{
reg int l,r;
scanf("%lld %lld",&l,&r);
printf("%lld\n",Calc(r)-Calc(l-1));
}
return 0;
}
```