最小数

题目链接：ybt金牌导航8-4-8

题目大意

给你一个整数 n ，要你找到只由 8 组成的被 n 整除的最小数的位数。

思路

考虑把这些数给表示出来。
（这里就给我整不会了）

\(\dfrac{8(10^x-1)}{9}\) 就是 \(x\) 位的那个数。

然后就可以有式子搞了：
\(\dfrac{8(10^x-1)}{9}\% n=0\)
然后左右和模数都乘 \(9\)：
\(8(10^x-1)\% 9n=0\)

显然就是要 \(10^x-1\%9n=0\)，即 \(10^x\equiv 1\pmod{9n}\)
（这里的 \(n\) 要除去它跟 \(8\) 的 \(\gcd\)）

发现这就是要找啊。
然后阶有一些性质：
有解的情况是下面的底数跟模数的 \(\gcd\) 是 \(1\)，即 \(\gcd(10,9n)=1\)。

然后阶是 \(\varphi(9n)\) 的，所以我们就直接在它的因子里面找。
（找的方法这里是每个质数分开考虑能不能删掉尽可能多个，因为阶的倍数肯定也满足条件）

然后这里有一个小小的优化（虽然没什么用），就是检查的时候你可以把指数 \(\% \varphi(9n)\)。（这个 \(n\) 是之前的）
因为欧拉定理，既然 \(10\) 和 \(9n\) 互质，就有 \(10^{\varphi(9n)}\equiv1\pmod{9n}\)。

然后搞就可以了。

代码

#include
#define ll long long

using namespace std;

ll n, tot, m, r, q, ans, num;

ll mul(ll x, ll y, ll mod) {
    ll z = (long double)x * y / mod;
    ll re = x * y - z * mod;
    if (re < 0) re += mod;
    if (re >= mod) re -= mod;
    return re;
}

ll ksm(ll x, ll y, ll mo) {
    ll re = 1;
    while (y) {
        if (y & 1) re = mul(re, x, mo);
        x = mul(x, x, mo);
        y >>= 1;
    }
    return re;
}

ll phi(ll now) {
    ll re = now;
    for (ll i = 2; i * i <= now; i++) {
        if (now % i == 0) {
            re = re / i * (i - 1);
            while (now % i == 0) now /= i; 
        }
    }
    if (now > 1) re = re / now * (now - 1);
    return re;
}

ll gcd(ll x, ll y) {
    if (!y) return x;
    return gcd(y, x % y);
}

ll check(ll y, ll mo) {
    return (ksm(10, y, mo) - 1 + mo) % mo * 8 % mo;
}

int main() {
    scanf("%lld", &n);
    while (n) {
        printf("Case %lld: ", ++tot);
        
        m = n * 9 / gcd(n, 8);
        r = phi(n * 9);
        
        if (gcd(10, m) != 1) printf("0\n");//判无解
            else {
                q = phi(m); ans = q;//阶肯定在 phi(m) 的约数中
                for (ll i = 2; i * i <= q; i++) {//每个质数分开考虑，每次能弃就弃
                    num = 0;
                    while (q % i == 0) q /= i, num++;
                    while (num && !check((ans / i) % r, n * 9))
                        num--, ans /= i;
                }
                if (q > 1 && !check((ans / q) % r, n * 9)) ans /= q;
                printf("%lld\n", ans);
            }
        
        scanf("%lld", &n);
    }
    
    return 0;
}