P3846:[TJOI2007]可爱的质数题解

BSGS 算法模板题

有\(a^{x} \equiv b (mod \; p)\),求\(x\)的值。我们可以来推下这个式子,首先,这个\(x \in [0, p]\),我们可以设\(x=im-j\),其中\(m=\lceil \sqrt{p} \rceil\)。显然,\(j \in [0, m], i \in [1, m]\)。式子变成这个样子:

\[a^{im}\equiv a^j b (mod \; p)\]

然后我们只需要求出后半部分,压入 map 中,再枚举前半部分即可求出。

代码

// P3846.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll p, a, b;
ll quick_power(ll base, ll tim)
{
    ll tmp = 1;
    while (tim)
    {
        if (tim & 1)
            tmp = tmp * base % p;
        base = base * base % p;
        tim >>= 1;
    }
    return tmp;
}
map<ll, ll> hashTable;
int main()
{
    scanf("%lld%lld%lld", &p, &a, &b);
    a %= p;
    if (a == 0)
    {
        if (b == 0)
            printf("0");
        else
            printf("no solution");
        return 0;
    }
    hashTable.clear();
    ll m = ceil(sqrt(p));
    for (int j = 0, x = 1; j <= m; j++, x = x * a % p)
        hashTable[x * b % p] = j;
    ll unit = quick_power(a, m);
    for (int i = 1, x = unit; i <= m; i++, x = x * unit % p)
        if (hashTable.count(x))
        {
            printf("%lld", i * m - hashTable[x]);
            return 0;
        }
    printf("no solution");
    return 0;
}

发布者

Kal0rona

江西师大附中全机房最弱

发表评论

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