Loading [MathJax]/extensions/tex2jax.js

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 中,再枚举前半部分即可求出。

代码

Plain text
Copy to clipboard
Open code in new window
EnlighterJS 3 Syntax Highlighter
// 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;
}
// 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; }
// 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;
}

Leave a Reply

Your email address will not be published. Required fields are marked *