题目
题目描述
英文题目
Chinese people think of ‘$8$’ as the lucky digit. Bob also likes digit ‘$8$’. Moreover, Bob has his own lucky number $L$. Now he wants to construct his luckiest number which is the minimum among all positive integers that are a multiple of $L$ and consist of only digit ‘$8$’.
中文题意
给定一个正整数$L$($L\leqslant 2\times10^9$)
问至少有多少个$8$连在一起组成的正整数是$L$的倍数
输入输出格式
输入格式
每行一个正整数$L$($L\leqslant 2\times10^9$)
输出格式
对于每个$L$，输出至少有多少个$8$连在一起组成的正整数是$L$的倍数，格式参照样例。若不存在，输出$0$
输入输出样例
输入样例
8
11
16
0
输出样例
Case 1: 1
Case 2: 2
Case 3: 0
题解
$n$个$8$连在一起组成的正整数可以记为$\frac{8}{9}(10^x-1)$
所以题目就转化为求最小的$x$使得$L|\frac{8}{9}(10^x-1)$
设$d=gcd(L,8)$
$L|\frac{8}{9}(10^x-1)\iff9L|8(10^x-1)\iff\frac{9L}{d}|10^x-1\iff10^x\equiv1\pmod{\frac{9L}{d}}$
这题的关键在于一个结论：若正整数$a,n$互质，则满足$a^x\equiv1\pmod{n}$的最小整数$x_0$为$\varphi(n)$的约数
证明：
假设满足$a^x\equiv1\pmod{n}$的最小整数$x_0$不能整除$\varphi(n)$
设$\varphi(n)=qx_0+r(0\leqslant r<x_0)$
$\because a^{x_0}\equiv1\pmod{n}$
$\therefore a^{qx_0}\equiv1\pmod{n}$
又$\because a^{\varphi(n)}\equiv1\pmod{n}$（欧拉定理）
$\therefore a^{r}\equiv1\pmod{n}$，与$x_0$最小矛盾！
$\therefore$假设不成立，原命题成立
所以，我们只需要求出$\varphi(\frac{9L}{d})$，时间复杂度$\Theta(\sqrt{L}lnL)$
代码如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
using namespace std;
long long a[500000],n,p,ans,i;
int t,m;
long long gcd(long long a,long long b)
{
return b?gcd(b,a%b):a;
}
long long phi(long long n)
{
long long i,m=n;
for(i=2;i*i<=n;i++) if(n%i==0){
m=m/i*(i-1);
while(n%i==0) n/=i;
}
if(n>1) m=m/n*(n-1);
return m;
}
long long mul(long long a,long long b)
{
a%=n,b%=n;
long long c=(long double)a*b/n;
long long ans=a*b-c*n;
if (ans<0) ans+=n;
else if(ans>=n) ans-=n;
return ans;
}
long long power(long long a,long long b)
{
long long c=1;
for(;b;b>>=1){
if(b&1) c=mul(c,a);
a=mul(a,a);
}
return c;
}
int main()
{
while(cin>>n&&n){
n=9*n/gcd(8,n);
cout<<"Case "<<++t<<": ";
if(gcd(10,n)==1){
p=phi(n);
m=0;
for(i=1;i*i<=p;i++) if(p%i==0){
a[++m]=i;
if(i*i!=p) a[++m]=p/i;
}
sort(a+1,a+m+1);
for(i=1;i<=m;i++) if(power(10,a[i])==1) break;
cout<<a[i]<<endl;
}
else cout<<"0"<<endl;
}
return 0;
}