题解 CF955C 【Sad powers】

VenusM1nT

2020-11-20 20:41:47

Solution

先考虑 $\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; } ```