955C. Sad powers(思维)

题目链接：传送门

思路：对于1到n的满足$a^b=x$的数$x$（幂次$b$>1）。

我们可以将之分为两种，一种是$b=2$，另一种$b>2$且不是完全平方数的个数。

对于第一种情况($b==2$)，即我们计算完全平方数的个数，这部我们可以二分$O(logn)$

对于第二种情况($b>2$)，因为$b=3$时这样数最多只有$10^{18/3}=10^6$种，$b>3$的则更少，所以这种情况的数我们可以暴力预处理。

但是第二种情况可能有重复计算，我们去重即可。但是第一种情况和第二种情况可能也有重复计算，我们再筛去第二种情况的完全平方数。

这样我们计算$f(n)$即小于等于$n$，满足$a^b=x$的数，$O(logn)$计算出第一种情况即可，$O(n)-O(log1e6)$计算第二种情况的即可。

代码：

#include<bits/stdc++.h> #define mset(a,b) memset(a,b,sizeof(a)) using namespace std; typedef long long ll; vector<ll> _o,o; ll root(ll x) { ll ans=0; ll l=1,r=1e9; while(l<=r) { ll m=(l+r)/2; if(m*m<=x){ ans=m; l=m+1; } else r=m-1; } return ans; } ll f(ll n) { int ans=upper_bound(o.begin(),o.end(),n)-o.begin(); return ans+root(n); } void init() { ll U=1e18; for(ll i=2;i<=1000000;++i) { for(ll cur=i*i*i;cur<=U;cur*=i) { _o.push_back(cur); if(cur> U/i) break; } } sort(_o.begin(),_o.end()); _o.erase(unique(_o.begin(),_o.end()),_o.end()); for(ll &v:_o) { ll r=root(v); if(r*r==v) continue; o.push_back(v); } } ll solve(ll l,ll r) { return f(r)-f(l-1); } int main() { ios::sync_with_stdio(false);cin.tie(0); init(); int t; cin>>t; while(t--) { ll l,r; cin>>l>>r; cout<<solve(l,r)<<endl; } }

这里提供一种容斥，但是超时的思路。

满足$a^b=x$,的数的 $b$ 无非是$2,3,...63$，又因为所有合数(如6=2*3)，所以幂次为合数的数也是幂次为素数的数。

所以我们我们只需 $b$ 取$2,3,5,7,11...$即可。但是像幂次为$2,3$这样有重复计算，即幂次为$6$的，所以这里就用到容斥了，我们容斥的是幂次为$2,3,5,7,11,...$的数的个数。

对于$b>63$的我们不予处理，因为满足幂次为$>63$的数为0个，预处理后发现容斥里面的幂次的个数有$38$个。

但是要怎么计算1~n内幂次为$b$次的数的个数呢？

用$pow(n,1/b)$即可，不过因为有误差，所以我们需要检测前面或后面的是否满足$a^b\le b$。

#include<bits/stdc++.h> #define mset(a,b) memset(a,b,sizeof(a)) using namespace std; typedef long long ll; const int maxn=1e5+10; int num[1005],tot; int rc[maxn],cnt; int top; vector<int> prime; int book[1005]; bool check(ll a,ll b,ll n)//return a^b<=n { ll ans=1; for(ll i=1; i<b; ++i) { n/=a; } if(a <= n)return true; else return false; } void init() { book[1]=1; for(int i=2; i<=63; ++i) { if(!book[i]) { prime.push_back(i); for(int j=i*i; j<=63; j+=i) book[j]=1; } } tot=0; for(int p:prime) num[tot++]=p; cnt=0; rc[cnt++]=-1; for(int i=0; i<tot; ++i) { int k=cnt; for(int j=0; j<k; ++j) { ll m=num[i]*(rc[j] < 0? -1 *rc[j]:rc[j]); if(m > 63) continue; rc[cnt++]=m*(rc[j]<0?1:-1); } } } ll getnum(ll n,ll k)//take maximal a of a^k<=n { ll r=pow(1.0*n,1.0/k); while(!check(r,k,n)) --r; while(check(r+1,k,n)) ++r; return r-1; } ll getcnt(ll n) { if(n==0) return 0; if(n < 4) return 1; int top=0; ll m=n; ll ans=1; for(int i=1; i<cnt; ++i) { if(rc[i] < 0) ans-=getnum(n,rc[i]*-1); else ans+=getnum(n,rc[i]); } return ans; } int main() { ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); init(); ll l,r,t; cin>>t; while(t--) { cin>>l>>r; cout<<getcnt(r)-getcnt(l-1)<<endl; } return 0; }