问题描述:

我们要找出一个最小的 $L$ 的只由$8$构成的数,使它是$L$的整数倍。

输入:

由多组数据,每组数据一个数 $L$,输入以$0$结束 $L$($1≤L≤2000000000$)

输出:

一个数,表示数字的长度。如果不存在则输出$0$

思路:

一道比较玄学的题。这种只由一种数字构成相关问题都是一个套路吧。

先是将$8888…8$看成$(10^k-1)/9*8$。于是 $9L|8(10^k-1)$,等价为$10^k \equiv 1 (mod \frac{9L}{gcd(8, L)})$,这是一步特别重要的转化。

然后有这样的一个模型:若正整数$a, n$互质,那么满足$a^k \equiv 1 (mod n)$ 的最小正整数$k_0$一定是$ \varphi (n)$ 的约数。

因此,$k$一定为 $\varphi ( \frac{9L}{gcd(8, L)} ) $的约数。然后我们就可以枚举约数,再使用快速幂验证就OK了。有一个细节就是 $\varphi (n)$会大于MAX_INT所以要注意要再用快速乘防止爆$long long$。

代码:

#include 
#include 
#include 
#include 
#define LL long long
using namespace std;

LL l, Case, fac[20000005];

LL gcd(LL x, LL y)
{
    return y==0 ? x : gcd(y, x%y);
}

LL phi(LL n)
{
    LL ans=n;
    for(LL i=2; i*i<=n; i++)
        if(n%i==0)
        {
            ans=ans/i*(i-1);
            while(n%i==0) n/=i;
        }
    if(n>1) ans=ans/n*(n-1);
    return ans;
}

LL ksc(LL x, LL y, LL p)
{
    LL ans=0;
    x%=p; y%=p;
    while(y)
    {
        if(y&1) ans=(ans+x)%p;
        x=(x+x)%p; y>>=1;
    }
    return ans;
}

LL ksm(LL x, LL y, LL p)
{
    LL ans=1;
    while(y)
    {
        if(y&1) ans=ksc(ans, x, p);
        x=ksc(x, x, p); y>>=1;
    }
    return ans;
}

int main()
{
    while(scanf("%lld", &l) && l)
    {
        int flag=0, cnt=0;;
        LL t1=l*9/gcd(l, 8);
        LL t2=phi(t1);
        for(LL i=1; i*i<=t2; i++)
            if(t2%i==0) fac[++cnt]=i, fac[++cnt]=t2/i;
        sort(fac+1, fac+cnt+1);
        for(LL i=1; i<=cnt; i++)
            if(ksm(10, fac[i], t1)==1)
            {
                printf("Case %lld: %lld\n", ++Case, fac[i]);
                flag=1;
                break;
            }
        if(!flag) printf("Case %lld: 0\n", ++Case);
    }
}

发表评论

邮箱地址不会被公开。 必填项已用*标注