CF955C 朴素简单做法

· · 题解

注意到，本题是容斥，很显然看出来和唯一分解有关系。稍微思考一下，其实本题就是莫比乌斯函数板子题。每次二分小于 n 的所有 a^k 最大的 a 来计算个数即可。

然后你就喜提 TLE 了，显然这个题略微有点卡常。这里给一个比较简单的卡常方法，在二分时，发现随着 k 的增大 a 的最大值是会以一个及其快的速度衰减的。所以，可以把对于每个 k 时 a 的最大值存下来作为二分。写完后发现跑得飞快。

然后就是代码了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mu[74]={0,0,1,1,0,1,-1,1,0,0,-1,1,0,1,-1,-1,0,1,0,1,0,-1,-1,1,0,0,-1,0,0,1,1,1,0,-1,-1,-1,0,1,-1,-1,0,1,1,1,0,0,-1,1,0,0,0,-1,0,1,0,-1,0,-1,-1,1,0,1,-1,0,0};
const int maxx[74]={0,0,1000000000,1000000,31622,3981,1000,372,177,100,63,43,31,24,19,15,13,11,10,8,7,7,6,6,5,5,4,4,4,4,3,3,3,3,3,3,3,3,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,1,1,1,1,1};
bool check(ll a,int b,ll n)
{
    ll sum=1;
    while(b)
    {
        if(b&1)
        {
            if((__int128)sum*a>n)
                return false;
            sum*=a;
        }
        b>>=1;
        if((__int128)a*a>n&&b)
            return false;
        a*=a;
    }
    return true;
}
ll calc(ll n)
{
    if(!n)
        return 0;
    ll ans=1;
    for(int i=2;i<=64;i++)
    {
        int l=1,r=maxx[i];
        while(l<r)
        {
            int mid=l+(r-l+1)/2;
            if(check(mid,i,n))
                l=mid;
            else
                r=mid-1;
        }
        ans+=mu[i]*(l-1);
    }
    return ans;
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        ll l,r;
        scanf("%lld%lld",&l,&r);
        printf("%lld\n",calc(r)-calc(l-1));
    }
    return 0;
}