题意：

给出一个数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
     
      #include
      
       #include
       
        #define N 1000001using namespace std;typedef long long ll;ll pri[N],tot;bool vis[N];void init(){	for(ll i=2;i
        
         >=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\n",c++,Ans(q));	}	return 0;}