【题目链接】
http://poj.org/problem?id=3696
【算法】
设需要x个8
那么，这个数可以表示为 ： 8(10^x - 1) / 9, 由题， L | 8(10^x - 1) / 9
令d = gcd(L,8)，则 ：
L | 8（10^x - 1) / 9
9L | 8 (10^x - 1) -> 9L/d | 10^x-1 -> 10^x(mod (9L/d)) = 1
易证a^x(mod n) = 1的最小正整数解是phi(n)的一个约数
那么，求出欧拉函数phi(9L/d),枚举约数，即可
【代码】
#include <algorithm>
#include <bitset>
#include <cctype>
#include <cerrno>
#include <clocale>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <limits>
#include <list>
#include <map>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <utility>
#include <vector>
#include <cwchar>
#include <cwctype>
#include <stack>
#include <limits.h>
using namespace std;
typedef long long ll; int i,cnt,TC;
ll factor[];
ll d,l,p; inline ll gcd(ll x,ll y)
{
if (y == ) return x;
else return gcd(y,x%y);
}
inline ll phi(ll n)
{
int i;
ll ret = n;
for (i = ; i <= sqrt(n); i++)
{
if (n % i == )
{
ret = ret / i * (i - );
while (n % i == ) n /= i;
}
}
if (n > ) ret = ret / n * (n - );
return ret;
}
inline ll mul(ll a,ll b,ll p)
{
ll ans = ;
while (b)
{
if (b & ) ans = (ans + a) % p;
a = a * % p;
b >>= ;
}
return ans;
}
inline ll power(ll a,ll n)
{
ll b = a,ret = ;
while (n > )
{
if (n & ) ret = mul(ret,b,d);
b = mul(b,b,d);
n >>= ;
}
return ret;
} int main()
{ while (scanf("%lld",&l) != EOF && l)
{
d = * l / gcd(,l);
printf("Case %d: ",++TC);
if (gcd(,d) != )
{
printf("0\n");
continue;
} else
{
cnt = ;
p = phi(d);
for (i = ; i <= sqrt(p); i++)
{
if (p % i == )
{
factor[++cnt] = i;
if (i * i != p) factor[++cnt] = p / i;
}
}
sort(factor+,factor+cnt+);for (i = ; i <= cnt; i++)
{
if (power(,factor[i]) == )
{
printf("%lld\n",factor[i]);
break;
}
}
}
} return ; }