最幸运的数字

AcWing-202-最幸运的数字

分析

见《进阶指南》第150页。

实现

#include <iostream>
#define inf 1e18
using namespace std;

typedef long long LL;

int gcd (int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}
LL phi (LL x) {
    LL res = x;
    for (int i = 2; i <= x / i; ++ i) {
        if (x % i == 0) {
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    }
    if (x > 1) res = res / x * (x - 1);
    return res;
}
LL mul (LL a, LL b, LL p) {
    LL res = 0;
    while (b > 0) {
        if (b & 1) res = (res + a) % p;
        a = a * 2 % p;
        b /= 2;
    }
    return res;
}
LL power (LL a, LL b, LL p) {
    LL res = 1 % p;
    while (b > 0) {
        if (b & 1) res = mul(res, a, p);
        a = mul(a, a, p);
        b /= 2;
    }
    return res;
}

int main () {
    int T = 0;
    LL L;
    while (cin >> L && L) {
        LL d = gcd(L, 8), C = 9 * L / d, p = phi(C);

        LL res = inf;
        if (C % 2 == 0 || C % 5 == 0) {
            res = 0;
        } else {
            for (int d = 1; d <= p / d; ++ d) {
                if (p % d == 0) {
                    if (power(10, d, C) == 1) res = min(res, (LL)d);
                    if (power(10, p / d, C) == 1) res = min(res, p / d);
                }
            }
        }
        cout << "Case " << ++ T << ": " << res << endl;
    }
    return 0;
}