> #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得不行了 (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