输入

1999999999
1213131311
1242342334
0

正确的输出

Case 1: 161290320
Case 2: 86628954
Case 3: 621171166

快速幂的模数很大，因此会爆 long long。

卡掉以下三篇题解：

题解 1

题解 2

题解 3

附上本人正确代码：

#include <cstdio>
#include <vector>
#include <algorithm>
#define ll long long
#define lll __int128
#define rep(i, s, t) for(int i=s; i<=t; ++i)
#define debug(x) cerr<<#x<<":"<<x<<endl;
#define gcd __gcd
const int N=100010;
using namespace std;

ll qp(ll x, ll y, ll mod)
{
    ll res=1;
    for(; y; y>>=1, x=(lll)x*x%mod) if(y&1) res=(lll)res*x%mod;
    return res;
}
ll n; vector<ll> d;
ll phi(ll x)
{
    ll res=x;
    rep(i, 2, x/i) if(x%i==0)
    {
        res=res/i*(i-1);
        while(x%i==0) x/=i;
    }
    if(x>1) res=res/x*(x-1);
    return res;
}

void solve()
{
    n=n/gcd(n, 8ll)*9;
    ll x=phi(n);
    rep(i, 1, x/i) if(x%i==0) d.push_back(i), d.push_back(x/i);
    sort(d.begin(), d.end());
    bool ok=0;
    for(ll x:d)
    {
        if(qp(10, x, n)==1)
        {
            printf("%lld\n", x); ok=1; break;
        }
    }
    if(!ok) puts("0");
}

int main()
{
#ifdef Jerrywang
    freopen("in.txt", "r", stdin);
#endif
    int cnt=0;
    while(scanf("%lld", &n), n) printf("Case %d: ", ++cnt), solve();
    return 0;
}