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^5

# 数学 + 子问题

若 $k$ 的最后一位为 $0,2,4,5,6,8$，直接返回 $-1$

• 因为上述任意一个数 $\times j \in [0\sim 9]$，都不可能为 $1$

例如：$k = 26$，需要从整数 $111$ 开始计算，$111\, mod\,k = 100\,mod\,k + 11\,mod\,k$

• $100\,mod\,k = (10 \,个\,10\,mod\,k\, 相加)\,mod\,k = 10 * (10\, mod\,k)$
• $11\,mod\,k$ 又是重复的子问题

可以得出：$remainder = x + preRemainder$

每一次求出余数 $remainder$ 后，再看是否 $remainder == 0$ 即可

定义 $v$ 为初始的整数，首先求出满足 $\ge k$ 的最小仅包含 $1$ 的整数 $v$。

初始化 $x = pow(10, v.length - 1)$

初始化 $remainder = v \,mod\, k$

其实可以用哈希表存储 $remainder$，若重复了直接返回 -1 即可，因为计算方式是一样的

class Solution {

    static Set<Character> set = new HashSet<>();

    public int smallestRepunitDivByK(int k) {

        // 0 2 5 6 8 都不行

        if (k % 2 == 0 || k % 5 == 0) {

            return -1;

        }

        String s = String.valueOf(k);

        int n = s.length();

        // 初始整数：例如 k = 41，v = 111

        int v = get(n);

        v = v < k ? v + (int) Math.pow(10, n) : v;

        int remainder = v % k;

        // 初始 x：例如 k = 40, l = 100 % 40 = 60

        int x = (int) Math.pow(10, String.valueOf(v).length() - 1) % k;

        int len = String.valueOf(v).length();

        // 此时必然有解

        while (remainder != 0) {

            x = 10 * x % k;

            remainder = (remainder + x) % k;

            len++;

        }

        return len;

    }

    public int get(int n) {

        int ans = 1;

        for (int i = 1; i < n; i++) {

            ans = (int) Math.pow(10, i) + ans;

        }

        return ans;

    }

}

# 优化

例如：$k = 26$，需要从整数 $111$ 开始计算

上述：$111\, mod\,k = 100\,mod\,k + 11\,mod\,k$

我们可以优化为：$111 \, mod \, k = 110\,mod\, k + 1 \, mod \, k$

• $110\,mod\,k = (10 \times (11 \,mod \,k))\,mod\,k$

class Solution {

    public int smallestRepunitDivByK(int k) {

        // 0 2 5 6 8 都不行

        if (k % 2 == 0 || k % 5 == 0) {

            return -1;

        }

        int len = 1;

        int remainder = 1 % k;

        while (remainder != 0) {

            remainder = (10 * remainder + 1) % k;

            len++;

        }

        return len;

    }

}

# 复杂度分析

• 时间复杂度 ：$O(k)$，由鸽巢原理（抽屉原理），模 $k$ 的结果必然在 $[0, k - 1]$ 中，其中有 $k$ 个数字，若循环 $k$ 次没有找到 $k$，必然有重复的数字
• 空间复杂度 ：$O(1)$

# 欧拉定理优化

# 前言 (质因数分解 + 欧拉函数求解)

欧拉定理：若 $gcd(a,m) =1$，则 $a^{\varphi(m)} \equiv 1 (mod\,m)$

欧拉函数：即 $\varphi(n)$ ，表示的是小于等于 $n$ 和 $n$ 互质的数的个数。

例如：$\varphi(1) = 1$。

当 $n$ 是质数的时候，显然有 $\varphi(n) = n - 1$

欧拉函数的性质：

• 若 $p$ 为质数，则 $\varphi(p^n) = p^{n - 1}(p-1)$

  证明：在不大于 $p^n$ 地正整数中，不与之互质的只有 $p$ 的倍数：$p、2p、3p、...、p^{n-1}\cdot p$ ，共 $p^{n - 1}$ 个，则 $\varphi(p^n) = p^n - p^{n - 1} = p^{n-1}(p-1)$

• 若 $a,b$ 互质，则 $\varphi(a)\varphi(b) = \varphi(ab)$

如何求解 $\varphi(n)$ 呢？那么直接根据定义质因数分解的同时求就好了

• 求出 $n$ 的不同质因数个数 ：

  	public int breakDown(int n) {
  	int ans = 0;
  	// 一个合数可以有多个质因数相乘而得，那么就可以得出一个结论：大于根号 n 的质因数只有一个
  	// 所以可以将范围缩减到 根号 n
  	// 最后只要特判一下 n 是否大于 1 就可以了，如果是大于那么剩下的 n 就是最后一个大于根号 n 的质因数
  	for (int i = 2; i * i <= n; i++) {
  	if (n % i == 0) {
  	// 不断地除 i，直到不会被 i 整除
  	while (n % i == 0) {
  	n /= i;
  	}
  	ans++;
  	}
  	}
  	// 若最后 n 留下了一个素数
  	// 例如：n = 38，最后留下 n = 19
  	// - 38 = 2 * 19
  	if (n > 1) {
  	ans++;
  	}
  	return ans;
  	}

  例如：$n = 36$，

  • $i = 2,36 \,\%\, 2 == 0,18 \,\%\,2 == 0\Longrightarrow n = 9$ 。
  • $i = 3,9 \,\%\,3 == 0, 3\,\%\,3==0\Longrightarrow n = 1$

  即：$36=2*2*3*3$

求解 $\varphi(n)$：

将正整数质因数分解：$n=p^{k_1}_1p^{k_2}_2\cdots p^{k_n}_n$

由性质得出：$\varphi(n) = p^{k_1-1}_1(p_1-1)\cdot p^{k_2-1}_2(p_2-1)\cdots p^{k_n-1}_n(p_n-1)$

$\varphi(n) = p^{k_1}_1\cdot \frac{(p_1-1)}{p_1}\cdot p^{k_2}_2\cdot \frac{(p_2-1)}{p_2}\cdots p^{k_n}_n\cdot \frac{(p_n-1)}{p_n}\,$

$\varphi(n) = n\cdot \frac{(p_1-1)}{p_1}\cdot \frac{(p_2-1)}{p_2}\cdots \frac{(p_n-1)}{p_n}\,$

	public int phi(int n) {
	int ans = n;
	for (int i = 2; i * i <= n; i++) {
	if (n % i == 0) {
	// ans * (i - 1) / i
	// => ans * i / (i - 1) 防止溢出
	ans = ans / i * (i - 1);
	// 不断地除 i，直到不会被 i 整除
	while (n % i == 0) {
	n /= i;
	}
	ans++;
	}
	}
	if (n > 1) {
	ans = ans / n * (n - 1);
	}
	return ans;
	}

# 求解 (欧拉定理 + 欧拉函数求解 + 快速幂)

参考：三种算法 + 优化

快速幂算法：

如需求数 a 的幂次，此处 a 可以为数，常规做法需要对 a 进行不断的乘积即 a * a * a * ... 此处的时间复杂度将为 O (n)

以求 $3^{10}$ 的结果为例：

[优化步骤 1：]

易知：

$3^{10}=3*3*3*3*3*3*3*3*3*3$

$=9^5 = 9^4*9$

$=81^2*9$

$=6561*9$

基于以上原理，我们在计算一个数的多次幂时，可以先判断其幂次的奇偶性，然后：

• 如果幂次为偶直接 base (底数) 作平方，power (幂次) 除以 2

• 如果幂次为奇则底数平方，幂次整除于 2 然后再多乘一次底数

[优化步骤 2：]

对于以上涉及到 [判断奇偶性] 和 [除以 2] 这样的操作。使用系统的位运算比普通运算的效率是高的，因此可以进一步优化：

• 把 $power$ 变为 $(power\, \&\, 1) == 1$

• 把 $power = power / 2$ 变为 $power = power >> 1$

矩阵快速幂。时间 $O(log\,n)$，空间 $O(1)$:

	//a^x
	public int pow(int a, int x) {
	int ans = 1;
	int base = a;
	while (x > 0) {
	// 奇数，需要多乘以一个 a
	if ((x & 1) == 1) {
	ans *= base;
	}
	base *= base;
	x >>= 1;
	}
	return ans;
	}

设 $n$ 的长度为 $x$，则 $n = \frac{10^x - 1}9$

由于 $n$ 是 $k$ 的倍数，且 $10^x - 1 = 9n$，有 $10^x - 1$ 是 $9k$ 的倍数。

即 $(10^x - 1)\,mod \,9k = 0\Longrightarrow10^x \equiv 1(mod \,9k)$

由 $10^{\varphi(m)} \equiv 1 (mod\,m)$ 可以得出 $x$ 必然为 $\varphi(9k)$ 的因子

欧拉定理：若 $gcd(a,m) =1$，则 $a^{\varphi(m)} \equiv 1 (mod\,m)$

可以计算 $\varphi(9k)$ 并枚举其因子 $d$，并使用快速幂算法算出 $10^d\,mod\,9k$ 是否等于 $1$

class Solution {

    public int smallestRepunitDivByK(int k) {

        if (k % 2 == 0 || k % 5 == 0) {

            return -1;

        }

        // 求出质因子数目 phi (9 * k)

        int m = phi(9 * k);

        // 从小到大枚举不超过 sqrt (m) 的因子

        int i = 1;

        for (; i * i <= m; i++) {

            if (m % i == 0 && pow(10, i, 9 * k) == 1) {

                return i;

            }

        }

        // 必然有解

        // 从大到小枚举不低于 sqrt (m) 的因子

        //  因为 i 大则 m /i 小

        for (; ; i--) {

            if (m % i == 0 && pow(10, m / i, 9 * k) == 1) {

                return m / i;

            }

        }

    }

    public int phi(int n) {

        int ans = n;

        for (int i = 2; i * i <= n; i++) {

            if (n % i == 0) {

                // ans * (i - 1) / i

                //	=> ans * i / (i - 1) 防止溢出

                ans = ans / i * (i - 1);

                // 不断地除 i，直到不会被 i 整除

                while (n % i == 0) {

                    n /= i;

                }

            }

        }

        if (n > 1) {

            ans = ans / n * (n - 1);

        }

        return ans;

    }

    //a^x % mod

    public long pow(int a, int x, int mod) {

        long ans = 1;

        long base = a;

        while (x > 0) {

            // 奇数，需要多乘以一个 a

            if ((x & 1) == 1) {

                ans = ans * base % mod;

            }

            base = base * base % mod;

            x >>= 1;

        }

        return ans;

    }

}

# 复杂度分析

• 时间复杂度 ：$O(\sqrt k\,log\,k)$
• 空间复杂度 ：$O(1)$