题目描述
8 是中国的幸运数字,如果一个数字的每一位都由 8 构成则该数字被称作是幸运数字。
现在给定一个正整数 L,请问至少多少个 8 连在一起组成的正整数(即最小幸运数字)是 L 的倍数。
样例
输入格式
输入包含多组测试用例。
每组测试用例占一行,包含一个整数 L。
当输入用例 L=0 时,表示输入终止,该用例无需处理。
输出格式
每组测试用例输出结果占一行。
结果为 Case i:+一个整数 N,N 代表满足条件的最小幸运数字的位数。
如果满足条件的幸运数字不存在,则 N=0。
数据范围
1≤L≤2×109
输入样例:
8
11
16
0
输出样例:
Case 1: 1
Case 2: 2
Case 3: 0
算法1
参考文献
提高课5.3
C++ 代码
//author: A Fei
//trick: 快速幂那里会爆LL,要龟速乘。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
LL gcd(LL a, LL b)
{
return b ? gcd(b, a % b) : a;
}
LL euler(LL n)
{
LL res = n, t = n;
for(LL i = 2; i <= t / i; i ++)
{
if(t % i == 0)
{
while(t % i == 0) t /= i;
res = res / i * (i - 1);
}
}
if(t > 1) res = res / t * (t - 1);
return res;
}
LL qmul(LL a, LL k, LL mod)
{
LL res = 0;
while(k)
{
if(k & 1) res = (res + a) % mod;
k >>= 1;
a = (a + a) % mod;
}
return res;
}
LL qmi(LL a, LL k, LL mod)
{
LL res = 1;
while(k)
{
if(k & 1) res = qmul(res, a, mod);
k >>= 1;
a = qmul(a, a, mod);
}
return res;
}
int main()
{
LL T = 0, L;
while(cin >> L, L)
{
LL d = gcd(L, 8);
LL t = 9 * L / d;
LL ans = 1e18;
if(gcd(t, 10) != 1) ans = 0;
else
{
LL x = euler(t);
for(LL i = 1; i <= x / i; i ++)
if(x % i == 0 )
{
if(qmi(10, i, t) == 1)ans = min(ans, i);
if(qmi(10, x / i, t) == 1) ans = min (ans, x / i);
}
}
printf("Case %lld: %lld\n", ++T, ans);
}
}