最幸运的数字

同余方程 欧拉互质同余定理 质数筛 求约数 欧拉函数 转10x方转化 T4 https://www.acwing.com/problem/content/description/204/

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

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

输入格式

输入包含多组测试用例。

每组测试用例占一行，包含一个整数 $L$。

当输入用例 $L=0$ 时，表示输入终止，该用例无需处理。

输出格式

每组测试用例输出结果占一行。

结果为 Case i:+一个整数 $N$，$N$ 代表满足条件的最小幸运数字的位数。

如果满足条件的幸运数字不存在，则 $N=0$。

数据范围

$1\le L\le 2\times 10^9$

输入样例：

8
11
16
0

输出样例：

Case 1: 1
Case 2: 2
Case 3: 0

2 3 4 5 6 7 8 9 2 9 4 9 5 9 7 9 8 9

思路

给一个 L， 有可能存在 $\mathrm{8...}\mathrm{mod}L=0$ ，即多个8组成关于L的倍数。

x个8组成的数无论是存longlong还是用字符串都很麻烦， 考虑用一个公式来表示： $8\times \mathrm{1.....1}$ x个1 再用 9表示 1: $8\times \frac{\mathrm{9...9}}{9}$ 分子又可以用减法表示： $8\times \frac{10^x-1}{9}$ 至此就有一个更好处理的形式。接下来就是求：$L|8\frac{10^x-1}{9}$中满足条件的最小的x。

分母可以移过去：$9L|8(10^x-1)$。

因为 $9L$ 和 $8$ 都是常数， 而我们只是要求整除的情况， 可以把两者的最大公因子筛去， 这样就能去掉右边的8：$\frac{9L}{d}|10^x-1$ （d为 $gcd(L,8)$）。

式子左边设为常数 C， 那么就转化为： $10^x\equiv 1(\mathrm{mod}C)$ 求最小的正整数 x。

根据欧拉定理 $a^{\phi (n)}\equiv 1(\mathrm{mod}n)$ , 其中 $gcd(a,n)=1$， a与n互质， 满足这个条件的话等式成立。 对应到当前的题目就是当 10 和 C 不互质的时候无解。若互质， 则解就是 $\phi (C)$。

但这个解并不一定是最小正整数解。

有一个结论， 所有满足同余方程的正整数解x一定满足 $x|\phi (C)$, 一定是 $\phi (C)$ 的约数。

而 $\phi (C)$的约数很少， 直接枚举就行。

代码

#include <bits/stdc++.h>
using namespace std;
 
typedef long long LL;
 
LL L;
 
LL qmul(LL a, LL b, LL p)
{
    LL res = 0;
    while (b)
    {
        if (b & 1)
            res = (res + a) % p;
        a = (a + a) % p;
        b >>= 1;
    }
    return res;
}
 
LL qmi(LL a, LL b, LL p)
{
    LL res = 1;
    while (b)
    {
        if (b & 1)
            res = qmul(res, a, p);
        a = qmul(a, a, p);
        b >>= 1;
    }
    return res;
}
 
LL gcd(LL a, LL b)
{
    return b ? gcd(b, a % b) : a;
}
 
LL get_eurl(LL c)
{
    LL res = c;
 
    for (int i = 2; i <= c / i; i++)
    {
        if (c % i == 0)
        {
            while (c % i == 0)
                c /= i;
            res = res / i * (i - 1);
        }
    }
    if (c > 1)
        res = res / c * (c - 1);
    return res;
}
 
void solve()
{
    LL d = gcd(L, 8);
    LL c = L * 9 / d;
 
    if (c % 2 == 0 || c % 5 == 0)
    {
        cout << 0 << endl;
        return;
    }
    // cout << c << endl;
    LL phi = get_eurl(c);
    // cout << phi << endl;
 
    LL res = 1e18;
    for (LL i = 1; i <= phi/i; i++)
    {
        if (phi % i == 0)
        {
            if (qmi(10, i, c) == 1)
                res = min(res, i);
            if (qmi(10, phi / i, c) == 1)
                res = min(res, phi / i);
        }
    }
    cout << res << endl;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int kase = 1;
    while (cin >> L, L)
    {
        cout << "Case " << kase++ << ": ";
        solve();
    }
    return 0;
}