题解 P4028 【New Product】

皎月半洒花 · 2019-01-30 12:08:14 · 题解

一道比较裸的BSGS。

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

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

• 要判断是否合法，即

  • 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 ;
}