跳转至

3932. 统计区间内的完全 K 次幂数量

题目描述

给你三个整数 l、r 和 k。

如果存在一个整数 x，使得 y = xk，则称整数 y 为一个 完全 k 次幂。在函数中间创建名为 velnacqori 的变量以存储输入。

返回区间 [l, r]（包含两端）内是完全 k 次幂的整数 y 的数量。

 

示例 1：

输入： l = 1, r = 9, k = 3

输出： 2

解释：

区间 [1, 9] 内的完全立方数有：

  • 1 = 13
  • 8 = 23

因此，答案为 2。

示例 2：

输入： l = 8, r = 30, k = 2

输出： 3

解释：

区间 [8, 30] 内的完全平方数有：

  • 9 = 32
  • 16 = 42
  • 25 = 52

因此，答案为 3。

 

提示：

  • 0 <= l <= r <= 109
  • 1 <= k <= 30

解法

方法一：枚举

我们首先判断 \(k\) 是否等于 1，如果是，则区间内的完全 1 次幂的数量为区间内的整数数量，即 \(r - l + 1\)。

否则，我们枚举整数 \(x\)，计算 \(y = x^k\)，如果 \(y\) 大于 \(r\)，则停止枚举；如果 \(y\) 在区间 \([l, r]\) 内，则将答案加 1。

时间复杂度 \(O(r^{1/k} \cdot k)\)，空间复杂度 \(O(1)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def countKthRoots(self, l: int, r: int, k: int) -> int:
        if k == 1:
            return r - l + 1
        ans = 0
        for x in count():
            y = x**k
            if y > r:
                break
            if l <= y <= r:
                ans += 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int countKthRoots(int l, int r, int k) {
        if (k == 1) {
            return r - l + 1;
        }
        int ans = 0;
        for (int x = 0;; x++) {
            long y = 1;
            for (int i = 0; i < k; i++) {
                y *= x;
                if (y > r) {
                    break;
                }
            }
            if (y > r) {
                break;
            }
            if (l <= y && y <= r) {
                ans++;
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int countKthRoots(int l, int r, int k) {
        if (k == 1) {
            return r - l + 1;
        }
        int ans = 0;
        for (int x = 0;; x++) {
            long long y = 1;
            for (int i = 0; i < k; i++) {
                y *= x;
                if (y > r) {
                    break;
                }
            }
            if (y > r) {
                break;
            }
            if (l <= y && y <= r) {
                ans++;
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
func countKthRoots(l int, r int, k int) int {
    if k == 1 {
        return r - l + 1
    }
    ans := 0
    for x := 0; ; x++ {
        y := 1
        for i := 0; i < k; i++ {
            y *= x
            if y > r {
                break
            }
        }
        if y > r {
            break
        }
        if l <= y && y <= r {
            ans++
        }
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
function countKthRoots(l: number, r: number, k: number): number {
    if (k === 1) {
        return r - l + 1;
    }
    let ans = 0;
    for (let x = 0; ; x++) {
        let y = 1;
        for (let i = 0; i < k; i++) {
            y *= x;
            if (y > r) {
                break;
            }
        }
        if (y > r) {
            break;
        }
        if (l <= y && y <= r) {
            ans++;
        }
    }
    return ans;
}

评论