基础数学算法-最幸运的数字

题目-最幸运的数字

问题分析

题目的要求是$L|88...8$的$8$的最少位数
因为数字不好操作, 将$88...8$转换为
$$8\cdot 11...1$$
继续转化
$$8\cdot \frac{99...9}{9}=8\cdot \frac{10^x-1}{9}$$
也就是
$$L|8\cdot \frac{10^x-1}{9}$$
求最小的$x$

假设$\gcd (8,L)=d$有
$$\frac{9L}{d}|10^x-1$$

设$t=\frac{9L}{d}$, 得到同余式

$$10^x\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}t)$$

可以发现$10^x$与$t$必须互质, 也就是$10$与$t$必须互质, 也就是说$\gcd (10,t)\ne 1$无解

既然$10$与$x$互质, 那么有欧拉函数$a^{\varphi (n)}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}n)$, 但是题目要求的是最小位数, 欧拉函数无法保证最小

猜想: 设$x$是最小位数, 那么有$x|\varphi (t)$, 也就是说$x$是$\varphi (t)$的约数

证明: 假设$x$不是$\varphi (t)$的约数, 我们设$\varphi (t)=qx+r(0<r<x)$
因为有$10^x\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}t)$
那么有$10^{qx}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}t)$

因为$10^{\varphi (x)}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}t)=10^{qx}\cdot 10^r\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}t)$
也就是说$10^r\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}t)$, 因为$r<x$, 但是我们假设$x$是最小的位数, 矛盾
因此$\varphi (t)=qx$, 也就是说最小位数$x$是$t$的一个约数, 证毕

算法步骤

• 计算出$t=\frac{9L}{d}$
• 计算$\varphi (t)$
• 枚举$\varphi (t)$的所有约数
• 快速幂算法检查$10^c\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}t)$, $c$是$\varphi (t)$的约数

算法瓶颈在枚举约数, 算法时间复杂度$O(\sqrt{L})$

枚举约数可以使用质因数分解 + $dfs$, 算法时间复杂度是$O(d(n))$, 其中$d(n)$是约数个数, 也就是$(c_1+1)(c_2+1)...(c_k+1)$

代码实现

分解质因数 + $dfs$枚举约数优化生成约数代码

相较于直接枚举能快$100ms$左右

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef pair<LL, LL> PII;
const int N = 50010;

int L;
int primes[N], cnt;
bool st[N];
vector<PII> f;
vector<LL> divs;

void init(int n) {
   
    for (int i = 2; i <= n; ++i) {
   
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] <= n / i; ++j) {
   
            st[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

LL get_phi(LL n) {
   
    LL ans = n;
    for (int i = 0; primes[i] <= n / primes[i]; ++i) {
   
        int p = primes[i];
        if (n % p == 0) {
   
            ans = ans / p * (p - 1);
            while (n % p == 0) n /= p;
        }
    }
    if (n > 1) ans = ans / n * (n - 1);
    return ans;
}

LL gcd(LL a, LL b) {
   
    return b ? gcd(b, a % b) : a;
}

void dfs(int u, LL curr) {
   
    if (u == f.size()) {
   
        divs.push_back(curr);
        return;
    }

    LL p = f[u].first;
    for (int i = 0; i <= f[u].second; ++i) {
   
        dfs(u + 1, curr);
        curr *= p;
    }
}

LL mul(LL a, LL b, LL mod) {
   
    a %= mod;
    LL ans = 0;
    while (b) {
   
        if (b & 1) ans = (ans + a) % mod;
        a = (a + a) % mod;
        b >>= 1;
    }
    return ans;
}

LL q_pow(LL a, LL b, LL mod) {
   
    a %= mod;
    LL ans = 1;
    while (b) {
   
        if (b & 1) ans = mul(ans, a, mod);
        a = mul(a, a, mod);
        b >>= 1;
    }
    return ans;
}

void solve(int idx) {
   
    f.clear();
    divs.clear();

    LL d = gcd(8, L);
    LL t = (LL) 9 * L / d;

    if (gcd(10, t) != 1) {
   
        printf("Case %d: %d\n", idx, 0);
        return;
    }

    LL val = get_phi(t);

    LL j = val;
    for (int i = 0; primes[i] <= j / primes[i]; ++i) {
   
        int p = primes[i];
        if (j % p == 0) {
   
            int s = 0;
            while (j % p == 0) s++, j /= p;
            f.push_back({
   p, s});
        }
    }
    if (j) f.push_back({
   j, 1});
    dfs(0, 1);

    LL ans = 1e18;
    for (LL div : divs) {
   
        if (q_pow(10, div, t) == 1) ans = min(ans, div);
    }

    printf("Case %d: %lld\n", idx, ans);
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    init(N - 1);
    int T = 1;
    while (cin >> L, L) solve(T++);

    return 0;
}

直接枚举约数代码

注意因为数据范围非常大, get_phi函数输入类型是$longlong$, 并且快速幂过程中乘积会爆$longlong$, 需要龟速乘辅助快速幂计算

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;
const int N = 50010;

int L;
int primes[N], cnt;
bool st[N];

void init(int n) {
   
    for (int i = 2; i <= n; ++i) {
   
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] <= n / i; ++j) {
   
            st[i * primes[j]] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

LL get_phi(LL n) {
   
    LL ans = n;
    for (int i = 0; primes[i] <= n / primes[i]; ++i) {
   
        int p = primes[i];
        if (n % p == 0) {
   
            ans = ans / p * (p - 1);
            while (n % p == 0) n /= p;
        }
    }
    if (n > 1) ans = ans / n * (n - 1);
    return ans;
}

LL gcd(LL a, LL b) {
   
    return b ? gcd(b, a % b) : a;
}

LL mul(LL a, LL b, LL mod) {
   
    a %= mod;
    LL ans = 0;
    while (b) {
   
        if (b & 1) ans = (ans + a) % mod;
        a = (a + a) % mod;
        b >>= 1;
    }
    return ans;
}

LL q_pow(LL a, LL b, LL mod) {
   
    a %= mod;
    LL ans = 1;
    while (b) {
   
        if (b & 1) ans = mul(ans, a, mod);
        a = mul(a, a, mod);
        b >>= 1;
    }
    return ans;
}

void solve(int idx) {
   
    LL d = gcd(8, L);
    LL t = (LL) 9 * L / d;

    if (gcd(10, t) != 1) {
   
        printf("Case %d: %d\n", idx, 0);
        return;
    }

    LL val = get_phi(t);
    LL ans = 1e18;

    for (LL i = 1; i <= val / i; ++i) {
   
        if (val % i == 0) {
   
            LL d1 = i;
            LL d2 = val / i;
            if (q_pow(10, d1, t) == 1) ans = min(ans, d1);
            if (q_pow(10, d2, t) == 1) ans = min(ans, d2);
        }
    }

    printf("Case %d: %lld\n", idx, ans);
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    init(N - 1);
    int T = 1;
    while (cin >> L, L) solve(T++);

    return 0;
}