题解 P4861 【按钮】

P4861 按钮

分析一下题目，我们只关心个位，于是转化为求 K^{x} \equiv 1 \pmod m 。

复杂度允许，使用 BSGS 算法。

模板 P3846

我的 BSGS 算法学习笔记

并没有说 K 与 m 互质，但是考虑无解的情况，当且仅当 K 与 m 不互质。

证明：

以上同余方程等价于不定方程 K\times K^{x-1}-a\times m=1 。

有解时满足裴蜀定理，所以 \gcd(K,m)=1 。

也就是 K 与 m 互质。

输入时先判断一下是否有解，有解再跑 BSGS 。

主要是我不会 exBSGS 。

Code

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <map>

using namespace std;

map <int,int> _hash;
inline int BSGS(int a,int b,int p)
{
    b%=p;
    int t=ceil(sqrt(p)),val=1;
    for(int i=0;i<t;i++)
    {
        _hash[1ll*b*val%p]=i;
        val=1ll*val*a%p;
    }
    a=val; val=1;

    if(!a) return !b? 1:-1;
    for(int i=0,j;i<=t;i++)
    {
        j=_hash.find(val) == _hash.end()? -1:_hash[val];
        if(~j && i*t-j > 0) return i*t-j;
        val=1ll*val*a%p;
    }
    return -1;
}

int gcd(int a,int b) {return !b? a:gcd(b,a%b);}

int main()
{
//  freopen("work.in","r",stdin); freopen("work.out","w",stdout);
    int m,k;
    scanf("%d%d",&m,&k);
    if(gcd(m,k)^1) printf("Let's go Blue Jays!");
    else printf("%d",BSGS(k,1,m));
//  fclose(stdin); fclose(stdout);
    return 0;
}

一些 BSGS 的题：

• P2485 [SDOI2011]计算器
• P4454 [CQOI2018]破解D-H协议 题解
• P3306 [SDOI2013] 随机数生成器
• P4884 多少个1？

\text{Thank you for your reading !}