2018-team7-CF28

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

前两题比较水 

有点小坑

第三题数论做不出

题意：L到R中满足 a的p次==x的个数   1e18范围

显然答案为cal(r)-cal(l-1)

p=2
4 9 16 25 36 49 64 81 100 ...
可以发现个数为sqrt(x） 下取整

p=3 往上就可以枚举了 把不能开根的放入vector

{{{
#!C
#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<ll> v;
ll solve(ll x){
    return upper_bound(v.begin(),v.end(),x)-v.begin()+sqrt(x);
}
const ll MAXN = 1e18;
int main(){
    int q;
    cin>>q;
    for(ll i=2;i<=1000000;++i){
        ll j= i*i;
        while(j<=MAXN/i){
            j*=i;
            ll s = sqrt(j);
            if(s*s!=j)v.push_back(j);
        }
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    while(q--){
        ll l,r;
        cin>>l>>r;
        cout<<solve(r)-solve(l-1)<<endl;
    }
    return 0;
}


}}}

刚开始看到幂次为2有1e9觉得不可做= =其实应该想到再往上一点的

前两题比较水

有点小坑

第三题数论做不出

题意：L到R中满足 a的p次==x的个数 1e18范围

显然答案为cal(r)-cal(l-1)

p=2

4 9 16 25 36 49 64 81 100 ...

可以发现个数为sqrt(x） 下取整

p=3 往上就可以枚举了 把不能开根的放入vector

#include <bits/stdc++.h>
using namespace std;
#define ll long long
vector<ll> v;
ll solve(ll x){
    return upper_bound(v.begin(),v.end(),x)-v.begin()+sqrt(x);
}
const ll MAXN = 1e18;
int main(){
    int q;
    cin>>q;
    for(ll i=2;i<=1000000;++i){
        ll j= i*i;
        while(j<=MAXN/i){
            j*=i;
            ll s = sqrt(j);
            if(s*s!=j)v.push_back(j);
        }
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    while(q--){
        ll l,r;
        cin>>l>>r;
        cout<<solve(r)-solve(l-1)<<endl;
    }
    return 0;
}

刚开始看到幂次为2有1e9觉得不可做= =其实应该想到再往上一点的