#include <iostream>
#include <cmath>
#include <algorithm>
#define MAXN 2147400000
using namespace std;
int primes[100000];
int prime_cnt;
__int64 L;
__int64 phi;
__int64 cur_divisor[50];
__int64 cur_divisor_mul[50];
int cur_divisor_alpha[50];
int cur_divisor_cnt;
__int64 divisors[1000];
int divisor_cnt;
__int64 pow10[100][2];

__int64 gcd(__int64 m,__int64 n)
{
	if(n==0) return m;
	if(m<n) return gcd(n,m);
	return gcd(n,m%n);
}

void calPrime()
{
	int sqrtN = (int)sqrt((double)MAXN),i,j;
	prime_cnt = 1;
	primes[0] = 2;
	for(i=3;i<=sqrtN;i++)
	{
		for(j=0;j<prime_cnt && primes[j]*primes[j]<=i;j++)
			if(i%primes[j] == 0) break;
		if(j>=prime_cnt || primes[j]*primes[j]>i)
			primes[prime_cnt++] = i;
	}
}

void calPhi(__int64 num)
{
	int i;
	cur_divisor_cnt = 0;
	for(i=0;i<50;i++)
	{
		cur_divisor_alpha[i] = 0;
		cur_divisor_mul[i] = 1;
	}
	bool flag;
	for(i=0;i<prime_cnt && primes[i]*primes[i]<=num;i++)
	{
		flag = false;
		while(num % primes[i] == 0)
		{
			flag = true;
			cur_divisor[cur_divisor_cnt] = (__int64)primes[i];
			cur_divisor_mul[cur_divisor_cnt] = cur_divisor_mul[cur_divisor_cnt]*(__int64)primes[i];
			num = num/primes[i];
			cur_divisor_alpha[cur_divisor_cnt]++;
		}
		if(flag) cur_divisor_cnt++;
	}
	if(num>1)
	{
		cur_divisor_mul[cur_divisor_cnt] = cur_divisor[cur_divisor_cnt] = num;
		cur_divisor_alpha[cur_divisor_cnt] = 1;
		cur_divisor_cnt++;
	}
	phi = 1;
	for(i=0;i<cur_divisor_cnt;i++)
	{
		phi = phi * (cur_divisor_mul[i] - cur_divisor_mul[i]/cur_divisor[i]);
	}
}

void calDivisors()
{
	int tmp_cnt[50]={0},c=0,i,j;
	divisor_cnt = 1;
	divisors[0] = 1;
	while(true)
	{
		c = 0;
		tmp_cnt[c]++;
		while(tmp_cnt[c]>cur_divisor_alpha[c])
		{
			tmp_cnt[c] = 0;
			c++;
			if(c>=cur_divisor_cnt) return;
			tmp_cnt[c]++;
		}
		divisors[divisor_cnt] = 1;
		for(i=0;i<cur_divisor_cnt;i++)
			for(j=0;j<tmp_cnt[i];j++)
				divisors[divisor_cnt] = divisors[divisor_cnt] * cur_divisor[i];
		divisor_cnt++;
	}
}

void mod10Mul(const __int64 a[2], const __int64 b[2], __int64 res[2])
{
	__int64 r1,r2,r3,r4,r;
	r1 = (a[0] * b[0]) % L;
	r2 = (((__int64)100000000 * b[0]) % L * a[1]) % L;
	r3 = (((__int64)100000000 * b[1]) % L * a[0]) % L;
	r4 = (((__int64)100000000 % L) * ((__int64)100000000 % L)) % L * a[1] % L *b[1] % L;
	r = (r1+r2+r3+r4) % L;
	res[0] = r % (__int64)100000000;
	res[1] = r / (__int64)100000000;
}

int main()
{
	int t_cnt = 0,i,t_num;
	calPrime();
	__int64 power_mod,t_phi;
	while(scanf("%I64d",&L)!=EOF && L)
	{
		cur_divisor_cnt = 0;
		t_cnt++;
		L = L*(__int64)9/gcd(8,L);
		pow10[0][0] = (__int64)10%L;
		pow10[0][1] = 0;
		for(i=1;i<100;i++)
			mod10Mul(pow10[i-1],pow10[i-1],pow10[i]);
		if(gcd((__int64)10,L)>1)
		{
			printf("Case %d: 0\n",t_cnt);
			continue;
		}
		calPhi(L);
		t_phi = phi;
		calPhi(t_phi);
		calDivisors();
		sort(divisors,divisors+divisor_cnt);

		power_mod = 1;
		t_num = 0;
		
		for(i=0;i<divisor_cnt;i++)
		{
			__int64 cur = divisors[i],res[2]={1};
			int ti=0;
			while(cur>0)
			{
				if((cur & 1)) mod10Mul(res,pow10[ti],res);
				ti++;
				cur>>=1;
			}
			if(res[0] == 1 && res[1] == 0) break;
		}
		if(i>=divisor_cnt)
			printf("Case %d: 0\n",t_cnt);
		else printf("Case %d: %I64d\n",t_cnt,divisors[i]);
	}
	return 0;
}

• Re:实在不知道哪组数据错了，WA得不行了 (3686) DreamOfGame 2009-07-01 14:25:34
  • Re:实在不知道哪组数据错了，WA得不行了 (35) dynamic_study 2009-07-01 16:25:13
    • Re:实在不知道哪组数据错了，WA得不行了 (56) cpp0600648238 2009-07-01 20:47:46
  • Re:实在不知道哪组数据错了，WA得不行了 (42) cpp0600648238 2009-07-01 20:46:56