The Luckiest number

Chinese people think of '8' as the lucky digit. Bob also likes digit '8'. Moreover, Bob has his own lucky number L. Now he wants to construct his luckiest number which is the minimum among all positive integers that are a multiple of L and consist of only digit '8'.

Input

The input consists of multiple test cases. Each test case contains exactly one line containing L(1 ≤ L ≤ 2,000,000,000). 

The last test case is followed by a line containing a zero.

Output

For each test case, print a line containing the test case number( beginning with 1) followed by a integer which is the length of Bob's luckiest number. If Bob can't construct his luckiest number, print a zero.

Sample Input

8
11
16
0

Sample Output

Case 1: 1
Case 2: 2
Case 3: 0

 

题意：   我呢英语不好，就通俗易懂的解释一下了。比如说样例：输入11 输出为2，就是有一个数字只由8组成比如说8、88、888然后需要的是能除尽11的最小的数的8的个数显然是88. 

题解：   首先需要的是推出公式。像(11111,22222,33333.......），这样的数，我们能想到的是(10^n-1)/9*k,这个题k显然是8，然后他说能除尽L也就是说(10^n-1)/9*8/L 是一个整数，因为9与8没有公因数，所以(10^n-1)/9*8/L可以写成(10^n-1)/9*(L/gcd(8,L)),我们可以令m=9*(L/gcd(8,L)),那么上式就可以写成(10^n-1)/m，因为结果是整数，所以(10^n-1)%m=0,即10^n=1modm这就构造出了能用欧拉函数解决的问题了，(10^n-1)%m=0 可以写成(10^n%m-1%m)%m=0,即：10^n%m=1;这样的形式我们可以考虑10^phi(m)%m=1,这样还没有结束，因为这样求的不一定是最小的，我们需要对phi(m)的因数进行考虑，因为它的因数会影响它，设 k为phi(m)的因数 ，只需要找到 10^k%m=1的k值就可以了，但然找的是最小的那个满足条件的因数。。不懂的同学看一下代码。

 

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll dp[1000001]; //  开多少本人有点迷，总之大一点就好
ll gcd (ll a,ll b){
	return b==0? a:gcd(b,a%b);
}
ll get_euler(ll n){ // 欧拉函数
	ll res=n,a=n;
	for (ll i = 2; i*i<=a;i++){
		if(a%i==0){
			res=res/i*(i-1);
			while(a%i==0) a=a/i;
		}
	}
	if(a>1) res=res/a*(a-1);
	return res;
}
ll mul(ll a,ll b,ll c)//骚快速幂
{
	ll ans=0;
	while(b)
	{
		if(b&1)
		{
			ans=(ans+a)%c;
		}
		a=(a<<1)%c;
		b>>=1;
	}
	return ans;
}
ll quick(ll a,ll b,ll c) //骚快速幂
{  
    ll ans=1;     
    a=a%c;   
    while(b!=0)  
    {  
        if(b&1) ans=mul(ans,a,c);   
        b>>=1;   
        a=mul(a,a,c);  
    }  
    return ans;  
}  
int main(){
	ll n,i;
	int cas=0;
	while(cin >> n,n){
		ll tmp=9*n/gcd(8,n);
		if(gcd(10,tmp)!=1){  // 这里需要注意一下，欧拉函数x^n%m=1必须保证gcd(x,m)=1,否则无解
			printf("Case %d: 0\n",++cas);
		}
		else{
			ll ans=get_euler(tmp);
			ll size=0;
		    for(i=1;i*i<=ans;i++){//找因子
			    if(ans%i==0){
				    dp[size++]=i;
				    if(ans/i!=i){
					    dp[size++]=ans/i;
				    }
			    }
		    }
		    sort(dp,dp+size);//从小开始找
		    for (i = 0; i < size;i++){
		    	if(quick(10,dp[i],tmp)==1){
		    		break;
		    	}
	    	}
	    	printf("Case %d: %lld\n",++cas,dp[i]);
	    }
	}
	return 0;
}