「poj 3696」The Luckiest number (欧拉定理)

poj 3696
题意：给定$L$, 求最少几个$8$组成的数是$L$的倍数。
对于这个$8$数来说，他的表示方法可以是$\sum^{n-1}_{i=0} 8 \cdot 10^i$。这样明显很不方便，我们想到学数列时的表示方法，$\frac{8(10^x-1)}{9}$。
本题就是要求$L|\frac{8(10^x-1)}{9}$的最小$x$解。
我们将分数先消掉，得$9L|8(10^x-1)$，然后这个整除式等同于同余式$8(10^x-1) \equiv 0 \pmod {9L}$
再进行化简，得$10^x \equiv 1 \pmod {\frac{9L}{gcd(8,9L)}}$ (同余基本性质)

引理: $a^x \equiv 1 \pmod{n}$的最小正整数解为$\varphi(n)$的约数。

具体可以用反证法+设带余除法形式证明。

然后应用在本题就是求出对应的$\varphi$值然后用试除法找每个因子用最开始的同余式判断即可。注意快速幂的取模，由于是模意义下的。

本题数据大要快速乘解决溢出的问题

#include<cstdio> 
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<cmath>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;

LL kse = 0;

namespace flyinthesky {

    LL L;

    LL gcd(LL a, LL b) {
        return b == 0 ? a : gcd(b, a % b);
    }
    LL mul(LL a, LL b) {
        LL bs = a, ans = 0ll;
        while (b) {
            if (b & 1ll) ans = (ans + bs) % (L * 9ll);
            bs = (bs + bs) % (L * 9ll);
            b >>= 1ll;
        }
        return ans;
    }
    LL ksm(LL a, LL b) {
        LL bs = a, ans = 1ll;
        while (b) {
            if (b & 1ll) ans = mul(ans, bs);
            bs = mul(bs, bs);
            b >>= 1ll;
        }
        return ans;
    }
    LL getphi(LL x) {
        LL ans = x;
        for (LL i = 2ll; i * i <= x; ++i) {
            if (x % i == 0) {
                ans = ans / i * (i - 1ll);
                while (x % i == 0ll) x /= i;
            }
        }
        if (x != 1ll) ans = ans / x * (x - 1ll);
        return ans;
    }
    LL chk(LL x) {
        LL res = ksm(10ll, x);
        --res, res = (res + (L * 9ll)) % (L * 9ll); 
        res *= 8ll; res %= (L * 9ll);
        if (res == 0) return true;
        return false;
    }

    void clean() {
    }
    int solve() {
        clean();
        LL phi = getphi(9 * L / gcd(8ll, 9ll * L));
        LL ans = 9223372036854775807ll;
        for (LL i = 1ll; i * i <= phi; ++i) {
            if (phi % i == 0ll) {
                if (chk(i)) ans = min(ans, i);
                if (phi / i != i) {
                    if (chk(phi / i)) ans = min(ans, phi / i);
                }
            }
        }
        if (ans == 9223372036854775807ll) cout << "Case " << ++kse << ": " << 0 << endl; else cout << "Case " << ++kse << ": " << ans << endl;
        return 0;
    }
}
int main() {
    while (scanf("%lld", &flyinthesky::L) && flyinthesky::L) flyinthesky::solve();
    return 0;
}