本文涉及知识点

数论：质数、最大公约数、菲蜀定理

LeetCode1015. 可被 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⁵

1015 整除

由于结果会大大超出uint64，所以无法直接运算。被整除也就是余数为0。
性质一： (10a+1)%k 等于 ((a%k)*10+1)%k。
通过性质一，我们可以将运算限制在int范围。
需要循环多次，一定能发现无解。k次。a初始为0，第k+1次后，a一定是重复值，也就是无限循环了。

代码

核心代码

	class Solution {
		public:
			int smallestRepunitDivByK(int k) {
				int a = 0;
				for (int i = 1; i <= k; i++) {
					a = (a * 10 + 1) % k;
					if (0 == a) { return i; }
				}
				return -1;
			}
		};

单元测试

int k;
		TEST_METHOD(TestMethod11)
		{
			auto res = Solution().smallestRepunitDivByK(1);
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod12)
		{
			auto res = Solution().smallestRepunitDivByK(2);
			AssertEx(-1, res);
		}