最幸运的数

[LInk](202. 最幸运的数字 - AcWing题库)

题意

8 8 8 是中国的幸运数字，如果一个数字的每一位都由 8 8 8 构成则该数字被称作是幸运数字。

现在给定一个正整数 L L L，请问至少多少个 8 8 8 连在一起组成的正整数（即最小幸运数字）是 L L L 的倍数。

题解

​ 将题目转化为数学符号的形式即找到最小的 x x x满足 L ∣ 8 ( 1 0 x − 1 ) 9 L\mid \frac{8(10^{x}-1)}{9} L∣98(10x−1)​

即 9 L ∣ 8 ( 1 0 x − 1 ) 9L\mid8(10^x-1) 9L∣8(10x−1) ,设 d = g c d ( L , 8 ) d=gcd(L,8) d=gcd(L,8), 则 9 L d ∣ 8 d ( 1 0 x − 1 ) \frac{9L}{d}\mid\frac{8}{d}(10^x-1) d9L​∣d8​(10x−1), d d d是 9 L 和 8 9L和8 9L和8的最大公约数，因此 ( 9 L 8 , 8 d ) = = 1 (\frac{9L}{8},\frac{8}{d})==1 (89L​,d8​)==1，所以如果满足整除则应该

9 L 8 ∣ ( 1 0 x − 1 ) \frac{9L}{8}\mid(10^x-1) 89L​∣(10x−1),设 n = 9 L 8 n=\frac{9L}{8} n=89L​，则 9 L 8 ∣ ( 1 0 x − 1 ) → 1 0 x ≡ 1 ( m o d   n ) \frac{9L}{8}\mid(10^x-1)\rightarrow 10^x\equiv1(mod\ n) 89L​∣(10x−1)→10x≡1(mod n)。

欧拉定理

若(a,n)==1，则 a φ ( n ) ≡ 1 ( m o d   n ) a^{\varphi(n)}\equiv1(mod\ n) aφ(n)≡1(mod n)

发现我们要求的最小的 x x x一定是 φ ( n ) \varphi(n) φ(n)的一个约数

证明

假设存在一个最小的不是 φ ( n ) \varphi(n) φ(n)的约数解x，则 φ ( n ) = a x + r 且 0 < r < x \varphi(n)=ax+r且0<r<x φ(n)=ax+r且0<r<x

a x ≡ 1 ( m o d   n ) → a a x ≡ 1 ( m o d   n ) a^x\equiv1(mod\ n)\rightarrow a^{ax}\equiv1(mod\ n) ax≡1(mod n)→aax≡1(mod n)

a φ ( n ) ≡ 1 ( m o d   n ) → a a x + r ≡ 1 ( m o d   n ) → a r ≡ 1 ( m o d   n ) a^{\varphi(n)}\equiv1(mod\ n)\rightarrow a^{ax+r}\equiv1(mod\ n)\rightarrow a^r\equiv1(mod\ n) aφ(n)≡1(mod n)→aax+r≡1(mod n)→ar≡1(mod n)

有 r < x r<x r<x所以找到了一个更小的解，与假设矛盾因子，最小的解一定是 φ ( n ) \varphi(n) φ(n)的约数

因此找出 φ ( n ) \varphi(n) φ(n)的所有约数，判断一下是否成立即可，因为数据太大会爆 L L LL LL因此要用龟速乘

Code

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <set>
#include <queue>
#include <vector>
#include <map>
#include <bitset>
#include <unordered_map>
#include <cmath> 
#include <stack>
#include <iomanip>
#include <deque> 
#include <sstream>
#define x first
#define y second
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 1e5 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
#define tpyeinput int
inline char nc() {static char buf[1000000],*p1=buf,*p2=buf;return p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++;}
inline void read(tpyeinput &sum) {char ch=nc();sum=0;while(!(ch>='0'&&ch<='9')) ch=nc();while(ch>='0'&&ch<='9') sum=(sum<<3)+(sum<<1)+(ch-48),ch=nc();}
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int v = 0) {
    e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
LL L;
LL gcd(LL a, LL b) {
    return b ? gcd(b, a % b) : a;
}
LL mul(LL a, LL b, LL p) {
    LL res = 0;
    while (b) {
        if (b & 1) res = (res + a) % p;
        a = (a * 2) % p;
        b >>= 1;
    }
    return res;
}
LL qmi(LL a, LL b, LL p) {
    LL res = 1;
    while (b) {
        if (b & 1) res = mul(res, a, p);
        a = mul(a, a, p);
        b >>= 1;
    }
    return res;
}
LL get_phi(LL x) {
    LL res = x;
    for (int i = 2; i <= x / i; i ++ ) {
        if (x % i == 0) {
            while (x % i == 0) x /= i;
            res = res / i * (i - 1);
        }
    }
    if (x > 1) res = res / x * (x - 1);
    return res;
}
int main() {
    int id = 0;
    while (cin >> L, L) {
        LL n = 9 * L / gcd(8, L);
        LL phi = get_phi(n);
        if (gcd(10, n) != 1) {
            printf("Case %d: %lld\n", ++id, 0);
            continue ;
        }
        LL res = 1e18;
        for (LL i = 1; i <= phi / i; i ++ ) {
            if (phi % i == 0) {
                if (qmi(10, i, n) == 1) res = min(res, i);
                if (qmi(10, phi / i, n) == 1) res = min(res, phi / i);
            }
        }
        printf("Case %d: %lld\n", ++id, res);
    }
    return 0;
}