P10496 The Luckiest Number 题解

w9095 · 2024-05-18 12:01:42 · 题解

P10496 The Luckiest Number

UPD：被叉了，原因是快速幂可能模数很大会爆 long long，改成 __int128 就好了。

考虑用一种比较方便表达的方式表示全是 8 的数字。我们发现，长度为 x 的全是 8 的数字可以表示为 \frac{10^x-1}{9}\times 8。

根据题目要求，这个数字是 L 的倍数，所以有下面式子：

两边同时乘以 9 得到：

这个式子可以继续化简，考虑到 \gcd(L,8) 一定整除 8(10^x-1)，我们考虑在左边除以 \gcd(L,8)，右边消去常数 8：

由于没有什么关于这种式子的算法，所以我们改变式子的形式，把它变成同余式：

移项得：

转化为了高次不定方程，直接使用 exBSGS 解决。注意这题需要求出的是最小正整数解，所以 exBSGS 返回的答案必须大于 0。

#include <bits/stdc++.h>
using namespace std;
long long t,a,p,x,y,now=0;
map<long long,long long>h;
long long gcd(long long a,long long b)
{
    if(b==0)return a;
    else return gcd(b,a%b);
}

long long exgcd(long long a,long long b,long long &x,long long &y)
{
    if(b==0)
       {
        x=1,y=0;
        return a;
       }
    long long r=exgcd(b,a%b,x,y),d=x;
    x=y,y=d-a/b*y;
    return r;
}

long long power(long long a,long long p,long long mod)
{
    long long ans=1,x=a;
    while(p)
       {
        if(p&1)ans=(__int128)ans*x%mod;
        p>>=1;
        x=(__int128)x*x%mod;
       }
    return ans; 
}

long long bsgs(long long a,long long b,long long mod)
{
    h.clear();
    long long t=sqrt(mod)+1,now=1,inc=power(a,t,mod);
    if(a==0)
       {
        if(b==0)return 1;
        else return -1;
       }
    for(int i=0;i<=t-1;i++)h[(__int128)now*b%mod]=i+1,now=(__int128)now*a%mod;
    now=1;
    for(int i=1;i<=t;i++)
        {
        now=(__int128)now*inc%mod;
        if(h.count(now)>0&&((__int128)i*t-h[now]+1))return (__int128)i*t-h[now]+1;
        }
    return -1;
}

long long exbsgs(long long a,long long b)
{
    long long d=gcd(a,p),cnt=0,sum=1,ans=0;
    a%=p,b%=p;
    if(a==0)
       {
        if(b==0)return 1;
        else return -1;
       }
    while(d!=1)
       {
        if(b%d!=0)return -1;
        cnt++,p/=d,sum=(__int128)sum*(a/d)%p,b/=d;
        d=gcd(a,p);
        if(sum==b&&cnt!=0)return cnt;
       }
    exgcd(sum%p,p,x,y);
    x=(x%p+p)%p;
    ans=bsgs(a,(__int128)x*b%p,p);
    if(ans==-1)return -1;
    else return ans+cnt;
}

int main()
{
    while(1)
        {
            scanf("%lld",&a);
            if(a==0)break;
            p=9*a/gcd(a,8),now++;
            long long ans=exbsgs(10,1);
            if(ans==-1)printf("Case %lld: 0\n",now);
            else printf("Case %lld: %lld\n",now,ans);
        }
    return 0;
}