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

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

题目描述：

给出正整数 $k$ ，需要找出可以被 $k$ 整除的、仅包含数字 $1$ 的最小正整数 $n$ 的长度。如果不存在返回 $-1$ . $n$ 不符合 $64$ 位带符号整数。

数据范围：

$1\le k \le 10^5$

题解：

$n$ 会变得很大，不能直接构造，可以考虑使用余数，整除时余数等于 $0$ .

$(p + q)\mod n = ((p \mod n) + (q \mod n)) \mod n$

$(p\times q) \mod m = ((p \mod m) \times (q\mod m)) \mod m$

因此可以通过 $n = (n * 10 + 1) \mod k$ 来构造 $n$ 的余数。但是需要确定循环次数。因为 $\mod k$ ，因此余数只有 $[0,k-1]$ 共 $k$ 种。如果不能整数，那么就是 $[1,k-1]$ 只有 $k-1$ 种。循环 $k$ 次肯定会出现 $n$ 等于了前面某一次的结果，继续下去就会进入循环，因此循环 $k$ 次就行。

还可以使用 $n = (n + tmp) \mod k$ 来实现，对 $tmp$ 每次 $tmp = tmp \times 10 \mod k$ 。因为公式2， $tmp = ((tmp \mod k) \times (10 \mod k))\mod k$ 。同样根据鸽笼原理也会出现 $n$ 等于前面某一次结果的情况。

代码：

class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const int INF = 0x3f3f3f3f;
    int smallestRepunitDivByK(int k)
    {
        if (k % 2 == 0)
            return -1;
        int ans = 0;
        for (int i = 0; i < k; ++i)
        {
            ans = (ans * 10 + 1) % k;
            if (ans == 0)
                return i + 1;
        }
        return -1;
    }
};