题意：
给出一个数L。求一个最小的x。使长度为x的888...8这个数整除L。
无解输出0，L<=2*10^9；
题解：
即求满足下式的最小x值：
8/9*(10^x-1)==k*L (k为正整数)
8*(10^x-1)==k*9*L
为继续化简，求出r=gcd(L,8)。
8/r *(10^x-1)==k*9*L/r
由于8/r与9*L/r互质。9*L这个因式必在(10^x-1)中，所以原式即为：
10^x-1≡0(mod 9*L/r)
10^x≡1(mod 9*L/r)
设q=9*L/r。由欧拉定理得；
10^φ(q)≡1(mod q)
当gcd(q,10)==1时成立。不等于1时无解；
那么φ(q)就是满足题意的的一个解。
但这个解未必是最小的；
实际上。这里的答案也就是10对模q的指数，暂且记为ans；
有定理说明了对随意的d满足10^d≡1(mod q)时，d mod ans==0。
所以φ(q) mod ans == 0。
由于φ(q)可能非常大，不能直接枚举ans验证，就将φ(q)分解因式；
对全部的质因子i去验证φ(q)/i是否满足10^φ(q)/i≡1(mod q)。
一直枚举完质因子，最后得到的就是ans。
程序实现方面。gcd没什么问题；
为了更快的分解因数(φ函数和最后求解都要用)，能够预处理一个素数表(大小到10^5就够了)。
验证模线性方程要用到高速幂，可是由于取模数在10^10量级，乘法时有溢出long long的可能。
所以高速幂要套个高速乘。也是一样取模q；
求解上面说了，不再赘述。
代码：
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define N 1000001
using namespace std;
typedef long long ll;
ll pri[N],tot;
bool vis[N];
void init()
{
for(ll i=2;i<N;i++)
{
if(!vis[i])
pri[++tot]=i;
for(ll j=1;j<=tot&&i*pri[j]<N;j++)
{
vis[i*pri[j]]=1;
if(i%pri[j]==0)
break;
}
}
}
ll gcd(ll a,ll b)
{
ll t=a%b;
while(t)
{
a=b,b=t;
t=a%b;
}
return b;
}
ll mul(ll x,ll y,ll mod)
{
ll ret=0;
while(y)
{
if(y&1)
ret=(ret+x)%mod;
x=(x+x)%mod;
y>>=1;
}
return ret;
}
ll pow(ll x,ll y,ll mod)
{
ll ret=1;
while(y)
{
if(y&1)
ret=mul(ret,x,mod);
x=mul(x,x,mod);
y>>=1;
}
return ret;
}
ll eular(ll x)
{
ll ret=x,i;
for(i=1;pri[i]*pri[i]<=x;i++)
{
if(x%pri[i]==0)
{
while(x%pri[i]==0)
x/=pri[i];
ret/=pri[i],ret*=pri[i]-1;
}
}
if(x!=1)
ret/=x,ret*=x-1;
return ret;
}
ll Ans(ll q)
{
if(gcd(q,10)!=1) return 0;
ll ret=eular(q),temp=ret,cnt;
for(ll i=1;pri[i]*pri[i]<=temp;i++)
{
if(temp%pri[i]==0)
{
cnt=0;
while(temp%pri[i]==0)
cnt++,temp/=pri[i];
while(cnt)
{
if(pow(10,ret/pri[i],q)==1)
{
ret/=pri[i],cnt--;
}
else
break;
}
}
}
if(temp!=1)
if(pow(10,ret/temp,q)==1)
ret/=temp;
return ret;
}
int main()
{
int c=1;
ll n,i,j,k,p,q;
init();
while(scanf("%lld",&n)&&n)
{
q=9*n/gcd(n,8);
printf("Case %d: %lld
",c++,Ans(q));
}
return 0;
}