该题没思路，参考了网上各种题解。。。。
注意到凡是那种11111..... 22222..... 33333.....之类的序列都可用这个式子来表示：k*(10^x-1)/9
进而简化：8 * (10^x-1)/9=L * k (k是一个整数)
8*(10^x-1)=9L*k
d=gcd(9L,8)=gcd(8,L)
8*(10^x-1)/d=9L/d*k
令p=8/d q=9L/d p*(10^x-1)=q*k
因为p,q互质，所以q|(10^x-1)，即10^x-1=0(mod q)，也就是10^x=1(mod 9*L/d)
由欧拉定理可知，当q与10互质的时候，10^(φ(q))=1 (mod q)，即必定存在一个解x。
而题目中要求的是最小的解，设为min，那么有a^min=1%q，因为要满足a^φ(q)=1%q，那么a^φ(q)肯定能变换成(a^min)^i。
所以接下来只要枚举φ(q)的因子，找出符合条件的最小者即可。
无解的时候就是q与10不互质的时候，因为若q与10有公因子d：
1.若d=2，q=2*k，那么10^x=2^x*5^x=1%2k
即2^x*5^x=1+2k*m，左边为偶数，右边为奇数，显然矛盾。
2.若d=5，q=5*k，那么10^x=2^x*5^x=1%5k
即2^x*5^x=1+5k*m，左边是5的倍数，右边不是5的倍数，显然矛盾。
#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#include <math.h> using namespace std;
long long L; long long gcd(long long a,long long b) {
return b==?a:gcd(b,a%b);
}
long long multi(long long a,long long b,long long mod) {
long long ret=;
while(b) {
if(b&)
ret=(ret+a)%mod;
a=(a<<)%mod;
b=b>>;
}
return ret;
}
long long quickPow(long long a,long long b,long long mod) {
long long ret=;
while(b) {
if(b&)
ret=multi(ret,a,mod); //直接相乘的话可能会溢出
a=multi(a,a,mod);
b=b>>;
}
return ret;
}
//求欧拉函数
long long eular(long long n) {
long long ret=,i;
for(i=; i*i<=n; i++) {
if(n%i==) {
n=n/i;
ret*=i-;
while(n%i==) {
n=n/i;
ret*=i;
}
}
}
if(n>)
ret*=n-;
return ret;
} int main() {
int t=;
while(scanf("%I64d",&L)!=EOF) {
if(L==)
break;
long long p=*L/gcd(L,);
long long d=gcd(,p);
if(d==) {
long long phi=eular(p);
long long ans=phi;
long long m=sqrt((double)phi);
bool flag=false;
//先枚举大小在1~sqrt(phi)之间的因子
for(int i=; i<=m; i++) {
if(phi%i== && quickPow(,i,p)==) {
ans=i;
flag=true;
break;
}
}
//若1~sqrt(phi)没找到符合的因子，那么枚举sqrt(phi)~phi之间的因子
if(!flag) {
for(int i=m; i>=; i--) {
if(phi%i== && quickPow(,phi/i,p)==) {
ans=phi/i;
break;
}
}
}
printf("Case %d: %I64d\n",++t,ans);
} else {
printf("Case %d: 0\n",++t);
}
}
return ;
}