前言

题目来源于省赛,OJ关了,分享一下结论 和 处理的方法

题意

多组测试数据,给定$L,R$ , 求区间$[L,R]$所有数的最大开根次数之和 即$M^K=i$

数据范围 : $1e18$

思路

我们考虑最大开次方数即 $log_2N$

这里可以使用换底公式得$\frac{logN}{log2}$

这样子我们就可以求出最大的以二为底的次幂

因为数据范围很大,我们并不能直接枚举每一个$i$

因此考虑使用前缀和优化

设$cnt[]$数组为$2-n$能开方$i$次的个数,(默认$1$的贡献是$1$

然后这里就有一个结论了

从$1-N$能被开$x$次方的数的个数为$pow(N,1.0/x)$

例如 :
$1-10$以内,$pow(N,1.0/3)=2$即$1,8$
$1-10$以内,$pow(N,1.0/2)=3$即$1,4,9$

显然是有重复的$1$,而且考虑$16$既可以开平方又可以开四次方,说明不仅有$1$

显然我们是要舍去的,因为题目要求的是最大的开次方数,因此我们都选 高次方的 如 : $16的四次方$

这样子我们就求出了,$2-N$中有多少可以开$i$次方的数,

所以最后计算答案只需要$cnt[i]*(i-1)$即可,因为我们还有 1次幂的数没有统计

为了方便统计最后 1次幂的数 ,我们对每一个大于$1$次幂的数都提出一个$1$

Code

const int N = 110;

int cnt[N];

int calc(int x){
    if(x < 2) return 1;
    memset(cnt, 0, sizeof cnt);
    int maxd = log(x) / log(2);
    for(int j = maxd ; j >= 2 ; j --){
        cnt[j] = pow(x, 1.0 / j) - 1;
        for(int k = 2 ; k * j <= maxd ; k ++)
            cnt[j] -= cnt[k * j];
    }
    int res = 0;
    for(int i = 2 ; i <= maxd ; i ++)
        res += cnt[i] * (i - 1);
    return res + x;
}

void solve(){
    int l, r;
    while(cin >> l >> r, l || r) {
        cout << calc(r) - calc(l - 1) << "\n";
    }
}