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

链接：1015.可被K整除的最小整数
难度：Medium
标签：哈希表、数学
简介：给定正整数 k ，你需要找出可以被 k 整除的、仅包含数字 1 的最 小 正整数 n 的长度。

题解 1 - cpp

• 编辑时间：2023-05-10
• 内存消耗：5.9MB
• 编程语言：cpp
• 解法介绍：欧拉函数。

typedef long long ll;
ll gcd(ll a, ll b) {
    if (a < b) return gcd(b, a);
    if (b == 0) return a;
    return gcd(b, a % b);
}
ll phi(ll n) {
    ll i = 2, x = n;
    while (i * i <= n) {
        if (x % i == 0) n -= n / i;
        while (x % i == 0) x /= i;
        i += 1;
    }
    if (x != 1) n -= n / x;
    return n;
}
ll quick_mul(ll a, ll b, ll mod) {
    ll ans = 0, temp = a;
    while (b) {
        if (b & 1) ans = (ans + temp) % mod;
        temp = (temp + temp) % mod;
        b >>= 1;
    }
    return ans;
}
ll quick_pow(ll a, ll b, ll mod) {
    ll ans = 1, temp = a;
    while (b) {
        if (b & 1) ans = quick_mul(ans, temp, mod) % mod;
        temp = quick_mul(temp, temp, mod) % mod;
        b >>= 1;
    }
    return ans;
}
set<ll> get_factors(ll num) {
    set<ll> s;
    ll i = 1;
    for (; i * i <= num; i++) {
        if (num % i == 0) {
            s.insert(i);
            s.insert(num / i);
        }
    }
    return s;
}
class Solution {
public:
    int smallestRepunitDivByK(int k) {
        if (gcd(10, 9 * k) != 1) return -1;
        k *= 9;
        ll n = phi(k);
        auto factors = get_factors(n);
        for (auto &num : factors) {
            if (quick_pow(10, num, k) == 1) return num;
        }
        return -1;
    }
};