题解 P4861 【按钮】

· · 题解

Solution For P4861

\mathsf{By\text{ }ShadderLeave}

Upd: 更新了代码部分，使其符合日报讲解

厚颜无耻宣传博客的同余方程笔记

题意简述

一个数字 1 在 M 进制下以最少的次数乘以 K 最后使个位为 1

分析

不要被所谓的 M 进制吓到了，M 进制的十位表达就是 M^1，个位就是没办法进位进到十位去的一部分，所以实际上就是求关于 x 的方程

K^x \equiv 1\pmod{M}

的最小整数解
题目没有保证 K,M 互质，但是我们依然选用 \mathsf{BSGS}，因为这题有解的时候都是满足 \gcd(K,M)=1 的

证明

K^x=a\times M+1 K\times K^{x-1}-a\times M=1

看做一个不定方程 ，只有 \gcd(K,M) | 1 的时候有解
所以 \gcd(K,M)\ne 1 时方程无解
证毕

那么套 \mathsf{BSGS} 板子求解，在一开始判 \gcd(K,M)\ne 1 的无解即可
\mathsf{BSGS} 的详细讲解那篇博客里有（超小声
设 x=i\times \sqrt{M}-j

对于同余方程 K^{i\times \sqrt{M}-j}\equiv 1\pmod{M}

即 \dfrac{K^{i\times \sqrt{M}}}{K^j}\equiv 1\pmod{M}

预处理分母，然后当模 M 意义下有 K^{i\times \sqrt{M}}=K^j 时\dfrac{K^{i \times \sqrt{M}}}{K^j}=1, 方程有解 i\times \sqrt{M}-j

分母怎么预处理呢？

因为我们的解形式是 i\times \sqrt{M}-j ，所以 j\in \left[0, \sqrt{M}\right)

预处理出 K^j\bmod M,j\in\left[0, \sqrt{M}\right) ,将其幂指数存在哈希表里面

暴力枚举 i,i\in\left[ 1,\sqrt{M}\right] ，对于每一个 K^{i\times \sqrt{M}} 在哈希表里面查询是否有对应的 K^j

若存在那么最小解就是 \boxed{i\times \sqrt{M}-\text{哈希表中存储的幂指数}}

\mathsf{Code:}

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
struct Hash_Table{ //手写的哈希表比map快很多
    static const LL MOD=233333;
    LL Hash[MOD+7],V[MOD+7],stk[MOD+7],top;
    Hash_Table() {memset(Hash,-1,sizeof(Hash));top=0;}
    inline void clear() {while(top) Hash[stk[top--]]=-1;return ;}
    inline void insert(LL val,LL mi)
    {
        LL h=val%MOD;
        while(Hash[h]!=-1&&Hash[h]!=val) ++h;
        Hash[h]=val;V[h]=mi;
        stk[++top]=h;
        return ;
    }
    inline LL find(LL val)
    {
        LL h=val%MOD;
        while(Hash[h]!=-1&&Hash[h]!=val) ++h;
        return Hash[h]==val?V[h]:-1;
    }
}H;
LL A,C;
inline LL gcd(LL a,LL b)
{
    return a%b==0?b:gcd(b,a%b);
}
inline LL fast_pow(LL b,LL k,LL m)
{
    LL s=1;
    while(k)
    {
        if(k&1) s=s*b%m;
        b=b*b%m;
        k>>=1;
    }
    return s;
}
inline LL BSGS()
{
    LL sqrtm=ceil(sqrt(C)),ti=1;
    for(int i=0;i<sqrtm;i++)//预处理出A^j
    {
        H.insert(ti,i);
        ti=ti*A%C;
    }
    LL t=ti=fast_pow(A,sqrtm,C),ans;
    for(int i=1;i<=sqrtm;i++)
    {
        if((ans=H.find(ti))!=-1)
            return i*sqrtm-ans;
        ti=ti*t%C;
    }
}
int main()
{
    scanf("%lld%lld",&C,&A);
    if(gcd(A,C)!=1)//无解
        printf("Let's go Blue Jays!");
    else printf("%lld",BSGS());
    return 0;
}

蟹蟹管理大大审核^_^

\huge\mathsf{The\text{ }End}