可被 K 整除的最小整数

1015. 可被 K 整除的最小整数

给定正整数 k ，你需要找出可以被 k 整除的、仅包含数字 1 的最小正整数 n 的长度。

返回 n 的长度。如果不存在这样的 n ，就返回-1。

注意： n 不符合 64 位带符号整数。

示例 1：

输入：k = 1
输出：1
解释：最小的答案是 n = 1，其长度为 1。

示例 2：

输入：k = 2
输出：-1
解释：不存在可被 2 整除的正整数 n 。

示例 3：

输入：k = 3
输出：3
解释：最小的答案是 n = 111，其长度为 3。

提示：

1 <= k <= 10⁵

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class Solution { public: int smallestRepunitDivByK(int k) { } };

python3 解法, 执行用时: 52 ms, 内存消耗: 15.9 MB, 提交时间: 2023-05-10 10:15:27

class Solution:
    def smallestRepunitDivByK(self, k: int) -> int:
        if k % 2 == 0 or k % 5 == 0:  # 如果 k 是 2 的倍数或者 5 的倍数，返回 -1
            return -1
        
        ans, resid = 1, 1  # ans 表示长度，resid 表示余数
        while resid % k != 0:  # 当余数不为 0 时
            resid = (resid % k) * (10 % k) + 1  # 模拟除法运算，计算下一次的余数
            ans += 1  # 长度加 1
            
        return ans  # 返回最小整数的长度

golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-05-10 10:14:31

// 计算欧拉函数（n 以内的与 n 互质的数的个数）
func phi(n int) int {
    res := n
    for i := 2; i*i <= n; i++ {
        if n%i == 0 {
            res = res / i * (i - 1)
            for n /= i; n%i == 0; n /= i {
            }
        }
    }
    if n > 1 {
        res = res / n * (n - 1)
    }
    return res
}

// 快速幂，返回 pow(x, n) % mod
func pow(x, n, mod int) int {
    x %= mod
    res := 1
    for ; n > 0; n /= 2 {
        if n%2 > 0 {
            res = res * x % mod
        }
        x = x * x % mod
    }
    return res
}

func smallestRepunitDivByK(k int) int {
    if k%2 == 0 || k%5 == 0 {
        return -1
    }
    m := phi(k * 9)
    // 从小到大枚举不超过 sqrt(m) 的因子
    i := 1
    for ; i*i <= m; i++ {
        if m%i == 0 && pow(10, i, k*9) == 1 {
            return i
        }
    }
    // 从小到大枚举不低于 sqrt(m) 的因子
    for i--; ; i-- {
        if m%i == 0 && pow(10, m/i, k*9) == 1 {
            return m / i
        }
    }
}

java 解法, 执行用时: 0 ms, 内存消耗: 38 MB, 提交时间: 2023-05-10 10:13:59

class Solution {
    public int smallestRepunitDivByK(int k) {
        if (k % 2 == 0 || k % 5 == 0)
            return -1;
        int m = phi(k * 9);
        // 从小到大枚举不超过 sqrt(m) 的因子
        int i = 1;
        for (; i * i <= m; i++)
            if (m % i == 0 && pow(10, i, k * 9) == 1)
                return i;
        // 从小到大枚举不低于 sqrt(m) 的因子
        for (i--; ; i--)
            if (m % i == 0 && pow(10, m / i, k * 9) == 1)
                return m / i;
    }

    // 计算欧拉函数（n 以内的与 n 互质的数的个数）
    private int phi(int n) {
        int res = n;
        for (int i = 2; i * i <= n; i++) {
            if (n % i == 0) {
                res = res / i * (i - 1);
                while (n % i == 0) n /= i;
            }
        }
        if (n > 1)
            res = res / n * (n - 1);
        return res;
    }

    // 快速幂，返回 pow(x, n) % mod
    private long pow(long x, int n, long mod) {
        long res = 1;
        for (; n > 0; n /= 2) {
            if (n % 2 > 0) res = res * x % mod;
            x = x * x % mod;
        }
        return res;
    }
}

python3 解法, 执行用时: 52 ms, 内存消耗: 15.9 MB, 提交时间: 2023-05-10 10:13:41

# 计算欧拉函数（n 以内的与 n 互质的数的个数）
def phi(n: int) -> int:
    res = n
    i = 2
    while i * i <= n:
        if n % i == 0:
            res = res // i * (i - 1)
            while n % i == 0:
                n //= i
        i += 1
    if n > 1:
        res = res // n * (n - 1)
    return res

class Solution:
    def smallestRepunitDivByK(self, k: int) -> int:
        if k % 2 == 0 or k % 5 == 0:
            return -1
        m = phi(k * 9)
        # 从小到大枚举不超过 sqrt(m) 的因子
        i = 1
        while i * i <= m:
            if m % i == 0 and pow(10, i, k * 9) == 1:
                return i
            i += 1
        # 从小到大枚举不低于 sqrt(m) 的因子
        i -= 1
        while True:
            if m % i == 0 and pow(10, m // i, k * 9) == 1:
                return m // i
            i -= 1

python3 解法, 执行用时: 48 ms, 内存消耗: 15.9 MB, 提交时间: 2023-05-10 10:13:20

class Solution:
    def smallestRepunitDivByK(self, k: int) -> int:
        if k % 2 == 0 or k % 5 == 0:
            return -1
        x = 1 % k
        for i in count(1):  # 一定有解
            if x == 0:
                return i
            x = (x * 10 + 1) % k

java 解法, 执行用时: 1 ms, 内存消耗: 38.1 MB, 提交时间: 2023-05-10 10:13:08

class Solution {
    public int smallestRepunitDivByK(int k) {
        if (k % 2 == 0 || k % 5 == 0)
            return -1;
        int x = 1 % k;
        for (int i = 1; ; i++) { // 一定有解
            if (x == 0)
                return i;
            x = (x * 10 + 1) % k;
        }
    }
}

golang 解法, 执行用时: 4 ms, 内存消耗: 1.8 MB, 提交时间: 2023-05-10 10:12:35

func smallestRepunitDivByK(k int) int {
    if k%2 == 0 || k%5 == 0 {
        return -1
    }
    x := 1 % k
    for i := 1; ; i++ { // 一定有解
        if x == 0 {
            return i
        }
        x = (x*10 + 1) % k
    }
}

golang 解法, 执行用时: 8 ms, 内存消耗: 5.9 MB, 提交时间: 2023-05-10 10:12:10

func smallestRepunitDivByK(k int) int {
    seen := map[int]bool{}
    x := 1 % k
    for x > 0 && !seen[x] {
        seen[x] = true
        x = (x*10 + 1) % k
    }
    if x > 0 {
        return -1
    }
    return len(seen) + 1
}

java 解法, 执行用时: 7 ms, 内存消耗: 43.1 MB, 提交时间: 2023-05-10 10:11:56

class Solution {
    public int smallestRepunitDivByK(int k) {
        var seen = new HashSet<Integer>();
        int x = 1 % k;
        while (x > 0 && seen.add(x))
            x = (x * 10 + 1) % k;
        return x > 0 ? -1 : seen.size() + 1;
    }
}

python3 解法, 执行用时: 44 ms, 内存消耗: 20.1 MB, 提交时间: 2023-05-10 10:11:43

class Solution:
    def smallestRepunitDivByK(self, k: int) -> int:
        seen = set()
        x = 1 % k
        while x and x not in seen:
            seen.add(x)
            x = (x * 10 + 1) % k
        return -1 if x else len(seen) + 1

上一题

下一题

详情