证明的话dalao都证明过了我放一份自己写的还算清晰的代码

时间复杂度

快速幂套慢速乘时间是log^2级别
太难分析具体值了，主要步骤就是分解欧拉函数然后检查，√*log^2级别的

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
long long factor[N];//约数数组
int gcd(int a,int b)//最大公约数
{
    return b?gcd(b,a%b):a;
}
long long mul(long long a,long long n,long long mod)//慢速乘
{
    long long res=0;
    while(n)
    {
        if(n&1)
            res=(res+a)%mod;
        a=(a<<1)%mod;
        n>>=1;
    }
    return res;
}
long long ksm(long long a,long long n,long long mod)//快速幂
{
    long long res=1%mod;
    while(n)
    {
        if(n&1)
            res=mul(res,a,mod);
        a=mul(a,a,mod);
        n>>=1;
    }
    return res;
}
long long phi(long long n)//求欧拉函数
{
    long long res=n;
    for(int i=2; i*i<=n; 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 divide(long long n)//分解约数
{
    int m=0;
    for(long long i=1; i*i<=n; i++)
    {
        if(n%i==0)
        {
            factor[m++]=i;
            if(n/i-i)
                factor[m++]=n/i;
        }
    }
    return m;
}

int main()
{
    long long n,T=0,ans;
    while(cin>>n,n)
    {
        n=n/gcd(n,8)*9;
        if(gcd(10,n)!=1)//判断10和9*L/gcd（8，L）是否互质，不互质就无解
            ans=0;
        else
        {
            long long p=phi(n);//求9*L/gcd（8，L）的欧拉函数
            int m=divide(p);//m是p的约数个数
            sort(factor,factor+m);//因为要从小到大枚举，分解约数之后的数组是乱序的
            for(int i=0;i<m;i++)
            {
                if(ksm(10,factor[i],n)==1)//检查答案是否正确，正确直接跳出
                {
                    ans=factor[i];
                    break;
                }
            }
        }
        cout<<"Case "<<++T<<": "<<ans<<endl;
    }
}