這個題很奇葩了。題意是給出個數(shù)字L，假如存在一個數(shù)K使得L*K = 888...，求888...的最小長度，如果不存在這樣的K，那么輸出0。
我是什么思路也沒有了，拖了幾天了，數(shù)論搞死我了，只能找答案了。
我看到個比較靠譜的推法。首先，888...=111...*8=(10^0+10^1+...+10^m-1)*8=(10^m - 1)/9*8，PS：m代表888...的長度。
好吧，終于化成指數(shù)了，現(xiàn)在有8*(10^m-1)/9=K*L，最小的m就是我們要求的答案啦。
方式1：
=> 8 * (10^m-1) = 9 * k * L
=> 8/d*(10^m-1)=9*k*L/d，d=gcd(8,9L)
=> 10^m-1 = 0 % 9 * L / gcd(8, 9L) = 0 % 9*L/gcd(8,L)，(由于gcd(8/d,9L/d)=1，那么10^m-1必然是9*L/d的倍數(shù)了)。
=> 10^m = 1 % 9 * L / gcd(8,L)
方式2：
=> 8*(10^m-1)/9 = 0 % L
=> 8*(10^m-1) = 0 % 9*L(這步的推出，比如x/9 = k*n，那么x=9*k*n了，顯然成立)
=> 10^m-1 = 0 % 9*L/gcd(9*L,8)，假如，d = gcd(9*L,8)，那么有8/d*(10^m-1)=k*9*L/d，因為8/d不可能是9 *L / d
的倍數(shù)，所以
10^m-1必定是9*L/d的倍數(shù)，所以10^m-1 = 0 % 9*L/gcd(9*L,8))，=>，10^m - 1 = 0 % 9 * L / gcd(L, 8),
(因為gcd(9,8)=1)。
=> 10^m = 1 % 9*L/gcd(8,L)
至此，2種方式都推出了，10^m = 1 % 9*L/gcd(8,L) 。
那么怎么解答這個問題了，這個就用到了歐拉定理了。令p = 9 * L / gcd(8,L)，那么有10^m = 1 % p。由歐拉定理知,Z*p中所有的
數(shù)字a均滿足a^euler(p) = 1 % p。那么，10只要是p的乘法群中就肯定有解了。如果，10不在Z*p中了，肯定是無解的。證明如下：
由a^x = 1%p，可以得到a^(x-1)*a=1%p，要a^(x-1)存在，那么gcd(a,p)|1，那么gcd(a,p)必須是1。
綜上所述，要滿足式子
a^m=1%p，必須gcd(p,a)=1，即a必須是p的乘法群中的數(shù)字。
現(xiàn)在的問題是求最小的m，由歐拉定理知道a^euler(p)=1%p，m再大就開始循環(huán)了。但是m可能會更小。比如，我們現(xiàn)在知道最小的m
是min，那么有a^min=1%p，因為要滿足a^euler(p)=1%p，那么a^euler(p)肯定能變換成
(a^min)^k,至于k是多少就不知道了，當然
也可以求出來。那么min就是euler(p)的一個因子，而且是最小的一個滿足a^min=1%p的因子了。
現(xiàn)在就可以通過枚舉euler(p)的因子，找到最小的因子min滿足式子a^min = 1 % p就能解決本問題了。
注意求a^m%p肯定是通過算法導論上面那種方法的,O(32)或者O(64)的復雜度，還有a*b%m也需要自己模擬，因為可能a*b就溢出了。
代碼如下，貌似代碼還可以通過其它的改進加快速度。
#include <stdio.h>
#include <math.h>
#include <algorithm>
#include <
string.h>
using namespace std;
typedef
long long INT;
//10^m = 1 % (9*L / gcd(8, L)),求最小m
//p = 9 * L / gcd(8,L)
//gcd(p,10) != 1則p有2或者5的因子,2^m=1%p或者
//5^m=1%p無解,原式無解
//if(p)素數(shù),m=euler(p) = p - 1
//否則,m一定是euler(p)的最小滿足等式的因子
//因為(10^m)^n = 10^euler(p) = 1%p
INT gcd(INT a, INT b)
{
if (a < b)swap(a, b);
while (b)
{
INT t = a;
a = b;
b = t % b;
}
return a;
}
INT Euler(INT nN)
{
INT nAns = 1;
INT nMax = sqrt((
double)nN) + 1;
for (INT i = 2; i <= nMax; ++i)
{
if (nN % i == 0)
{
nAns *= i - 1;
nN /= i;
while (nN % i == 0)
{
nAns *= i;
nN /= i;
}
}
}
if (nN != 1)nAns *= nN - 1;
return nAns;
}
INT MultMod(INT a, INT b, INT mod)
{
INT ans = 0;
while (b)
{
if (b & 1)
{
ans = (ans + a) % mod;
}
a = (2 * a) % mod;
b >>= 1;
}
return ans;
}
INT ExpMod(INT
base, INT exp, INT mod)
{
INT ans = 1;
base %= mod;
while (exp)
{
if (exp & 1)
{
ans = MultMod(ans,
base, mod);
}
base = MultMod(
base,
base, mod);
exp >>= 1;
}
return ans % mod;
}
INT GetAns(INT p)
{
INT u = Euler(p);
INT nMax = sqrt((
double)u) + 1;
INT nAns = u;
for (INT i = 1; i <= nMax; ++i)
{
if (u % i == 0)
{
if (ExpMod(10, i, p) == 1)
{
nAns = i;
break;
}
if (ExpMod(10, u / i, p) == 1)
{
nAns = min(nAns, u / i);
}
}
}
return nAns;
}
int main()
{
INT nL;
INT nCase = 1;
while (scanf("%I64d", &nL), nL)
{
INT p = 9 * nL / gcd(nL, 8);
if (gcd(p, 10) != 1)
{
printf("Case %I64d: 0\n", nCase++);
continue;
}
printf("Case %I64d: %I64d\n", nCase++, GetAns(p));
}
return 0;
}