_pks 'w blog

_pks 'w blog

除了勇气,我什么都不缺。

题解 P4028 【New Product】

posted on 2019-01-30 12:08:14 | under 题解 |

一道比较裸的 $BSGS$ 。

但事实上,这个题有一堆坑点。以下就列举一下:

在对式子 $$A^k \equiv B(\mod P~~)$$ 进行 $BSGS$ 时,

  • 要判断是否合法,即

    • $1$ 、要判断 $A$ 是不是 $P$ 的倍数,此处一定要判,因为当且仅当 $A$ 和 $P$ 互质的时候我们才可以拿费马小定理乱搞!
    • $2$ 、判断 $P-\sqrt P-1$ 是否非负。虽然光看式子的话他显然是不可能为负,但是代码中不一样。如果是负的话,不能进行 $expow$
  • 边界问题要注意。这个地方本人推荐 $\sqrt P$ 上取整,然后 $BSGS$ 内部选用 $\leq$ 做边界而不是 $<$ 。这个地方就牵扯到上面提到过的问题——当 $\sqrt P$ 上取整之后,式子 $P - \sqrt p -1$ 是可以 $< 0$ 的,所以这个地方我们多加一倍就行了:

    P = ceil(sqrt(p)), Q = expow(x, -P + 2 *(p - 1), p) ;
  • 关于 $map$ 的使用,笔者发现大家完全可以用 $unordered\_map$ 替换 $map$ ,毕竟我们只需要一个哈希表就够了。而 $unordered\_map$ 是真的快

剩下的大概就没啦~

#include <cmath>
#include <cstdio>
#include <iostream>
#include<tr1/unordered_map>

#define LL long long

using namespace std ; 
using namespace tr1 ; int T ;
LL A, B, M, P, Q ; unordered_map <LL, LL> Hash ;

inline LL expow(LL a, LL b, LL p){
    LL res = 1 ;
    while (b){
        if (b & 1) 
            (res *= a) %= p ;
        (a *= a) %= p, b >>= 1 ;
    }
    return res % p ;
}
inline void bsgs(LL x, LL y, LL p){
    P = ceil(sqrt(p)), Hash.clear(), Q = expow(x, -P + 2 *(p - 1), p) ;
    //a ^ (p-1) = 1 (mod p) => Q = a^(-P) = a ^(-P + p -1) ;
    for (LL i = 1, j = 0 ; j < P ; ++ j, (i *= x) %= p) 
        if (!Hash.count(i)) Hash[i] = j ; // Push them into hash_table
    for (LL i = y, j = 0  ; j <= P ; ++ j, (i *= Q) %= p) 
        if (Hash.count(i)){ cout << Hash[i] + j * P << endl ; return ; }
    cout << "Couldn't Produce!" << endl ;
}
inline LL qr(){
    LL res = 0 ; char c = getchar() ; while (!isdigit(c)) c = getchar() ;
    while (isdigit(c)) res = (res << 1) + (res << 3) + c - 48, c = getchar() ;
    return res ;
}
int main(){
    cin >> T ;
    while (T --){
        M = qr(), A = qr(), B = qr() ;
        if ((!(A % M == 0 && B))) bsgs(A, B, M) ;
        else cout << "Couldn't Produce!" << endl ; 
    }
    return 0 ;
}