题解 P4028 【New Product】
皎月半洒花
2019-01-30 12:08:14
一道比较裸的$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$的，所以这个地方我们多加一倍就行了：
```cpp
P = ceil(sqrt(p)), Q = expow(x, -P + 2 *(p - 1), p) ;
```
* 关于$map$的使用，笔者发现大家完全可以用$unordered\_map$替换$map$，毕竟我们只需要一个哈希表就够了。而$unordered\_map$是**真的快**！
剩下的大概就没啦~
```cpp
#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 ;
}
```