莫欺少年穷，修魔之旅在这开始—>算法提高课题解

思路：

$\begin{matrix}\underbrace{888\cdots888}\\\\x\end{matrix}=8\times\begin{matrix}\underbrace{111\cdots111}\\\\x\end{matrix}=8\times\dfrac{\begin{matrix}\underbrace{999\cdots999}\\\\x\end{matrix}}{9}=8\times\dfrac{10^x-1}{9}$

$所以\ L\mid 8\times\dfrac{10^x-1}{9}\Rightarrow 9L\mid 8\times(10^x-1)$

$令\ d=\gcd(8,L)，则\ 9L\mid 8\times(10^x-1)\Rightarrow \dfrac{9L}{d}\mid\dfrac{8}{d}\times(10^x-1)$

$因为\gcd(\dfrac{9L}{d},\dfrac{8}{d})=1，所以\dfrac{9L}{d}\mid(10^x-1)$

$令\ c=\dfrac{9L}{d}，则\ c\mid(10^x-1)，即\ 10^x\equiv1\pmod{c}$

$因为\ {10^{\phi(c)}}\equiv1\pmod{c}，易得\ x\ 是\ \phi(c)\ 的约数，故我们只需求出满足条件的最小的\ x\ 即可$

总结：

1. 先求出 d = gcd(8, L)
2. 令 c = 9 * L / d，获取 c 的欧拉函数 phi
3. 枚举 phi 的所有约数，找到满足条件的最小约数

完整代码：

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

//龟速乘，b 个 a 相加
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;
}

//快速幂，b 个 a 相乘
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;
}

//获取 n 的欧拉函数
LL get_euler(LL n)
{
    LL res=n;
    for(int i=2;i<=n/i;i++)
        if(n%i==0)
        {
            res=res/i*(i-1);
            while(n%i==0) n/=i;
        }

    if(n>1) res=res/n*(n-1);

    return res;
}

int main()
{
    int T=1;
    LL L;
    while(cin>>L,L)
    {
        int d=1;
        while(L%(d*2)==0&&d<=4) d*=2; //先求出 d = gcd(8, L)

        LL c=9*L/d; //令 c = 9 * L / d
        LL phi=get_euler(c); //获得 c 的欧拉函数

        LL res=1e18;
        if(c%2==0||c%5==0) res=0; // 10 和 c 必须互质
        else
        {
            for(LL i=1;i*i<=phi;i++) //枚举 phi 的所有约数，选择符合条件的最小数
                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);
                }
        }

        printf("Case %d: %lld\n",T++,res);
    }

    return 0;
}