题目

题目描述

原题

英文题目

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)$
代码如下：

#include<algorithm>
#include<iostream>
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;
}