POJ 3696 The Luckiest Number：歐拉定理解指數方程

題目轉化

求最小長度的全 8 數（如 8, 88, 888...）使其為 L 的倍數。即求最小 x 使 (10^x - 1)/9 * 8 ≡ 0 (mod L)，化簡得 10^x ≡ 1 (mod 9L/gcd(9L,8))。設模數 m = 9L / 2^k（去除因子 2），若 m 有因子 2 或 5 則無解。否則求 10 模 m 的階，即最小 x 使 10^x ≡ 1 (mod m)。由歐拉定理 x | φ(m)，枚舉 φ(m) 的約數找最小滿足者。

代碼 (C++)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll mul_mod(ll a, ll b, ll mod) {
    ll res = 0;
    while (b) { if (b & 1) res = (res + a) % mod; a = (a + a) % mod; b >>= 1; }
    return res;
}
ll pow_mod(ll a, ll n, ll mod) {
    ll res = 1; a %= mod;
    while (n) { if (n & 1) res = mul_mod(res, a, mod); a = mul_mod(a, a, mod); n >>= 1; }
    return res;
}
ll euler(ll n) {
    ll ret = n;
    for (ll i = 2; i * i <= n; i++)
        if (n % i == 0) {
            ret = ret / i * (i - 1);
            while (n % i == 0) n /= i;
        }
    if (n > 1) ret = ret / n * (n - 1);
    return ret;
}
int main() {
    ll L;
    while (cin >> L) {
        ll m = L * 9;
        while (m % 2 == 0) m /= 2;
        if (m % 2 == 0 || m % 5 == 0) { cout << 0 << endl; continue; }
        ll phi = euler(m);
        vector fac;
        for (ll i = 1; i * i <= phi; i++)
            if (phi % i == 0) { fac.push_back(i); if (i * i != phi) fac.push_back(phi / i); }
        sort(fac.begin(), fac.end());
        for (ll d : fac)
            if (pow_mod(10, d, m) == 1) { cout << d << endl; break; }
    }
    return 0;
}