_pks 'w blog

_pks 'w blog

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

题解 P4195 【【模板】exBSGS/Spoj3105 Mod】

posted on 2019-02-22 21:10:55 | under 题解 |

今天才发现原来 $\rm{BSGS}$ 有两种写法……并且觉得剩下的题解讲的都讲的不是很全的样子233。

其实本质上,当 $p$ 不为素数时,我们无法进行朴素 $\rm{BSGS}$ 的原因是我们的欧拉定理 $a^{\varphi(p)} \equiv b(\bmod p)$ 只能处理 $(a,p)=1$ 的情况。那么我们知道,朴素的 $\rm{BSGS}$ 的关键在于,可以保证最小解是有界的—— $x$ 一定在 $[1,\varphi(p)]$ 中。所以最后 $BSGS$ 的复杂度才会是 $\Theta(\sqrt{\varphi(p)})$ 的——比如说比较常见的 $p$ 是素数的情况下,时间复杂度为 $\Theta(p)$ 。

那么也就是说,我们只需要进行一些操作,保证 $(a,p)=1 $ 即可。

我们思考,对于同余式 $a^x\equiv b~(\bmod p)$ 而言,我们先假定 $(a,p)>1 $ 。而此时如果有 $((a,p), b)=1$ ,那么说明此式只有可能在 $x=0,b=1 $ 的时候有解——这个结论是平凡的。因为假设我们把它展开成 $a\cdot a^{x-1} +kp=b $ 的形式,必须要有 $(a,p) ~|~ b$ 的情况下,才能保证 $a^{x-1}$ 和 $k $ 都是整数。

那么对于 $(a,p)>1$ 且 $(a,p)~|~b $ ,我们令原式变成

$$ a^{x-1}\cdot \frac{a}{(a,p)} \equiv \frac{b}{(a,p)} (\bmod \frac{p}{(a,p)}) $$ 的样子,如果此时 $(a^{x-1},\frac{p}{(a,p)})=1$ 的话,我们就直接解

$$ a^{x-1}\equiv \frac{\frac{b}{(a,p)}} {\frac{a}{(a,p)} }(\bmod \frac{p}{(a,p)}) $$ 这个方程即可。否则我们继续分解直至 $(p',a)=1$ 。

那么此时有个问题需要注意,就是如果们在解这个方程时,出现了

$$ (a^{x-1}, \frac{p}{(a,p)})\nmid \frac{\frac{b}{(a,p)}} {\frac{a}{(a,p)} } $$ 的情况,那我们需要特判并return -1 ;另一种情况,如果我们出现了

$$ a^{x-1}\equiv \frac{\frac{b}{(a,p)}} {\frac{a}{(a,p)} } \equiv1(\bmod \frac{p}{(a,p)}) $$ 的情况,也需要特判并输出此 $k$ (此时同余式左边是 $a^{x-k}$ ,因为 $a^{x-k}\equiv1~(\bmod p)$ 所以直接输出 $k$ ),不过也有可能不需要,完全看你写的 $BSGS$ 能不能判断 $x=0$ 的情况……一般情况下不能。

算法流程大体就是这些。有些需要注意的是, $BSGS$ 有两种写法。我的这种写法是小步为 $a^j$ ,大步为 $a^{-im}b$ 。此时由于 $\bold{p}$ 不再是素数,所以不能用费马小定理,需要我们用 $exgcd$ 的方法求逆元,包括但不限于 $\frac{b}{(a,p)}$ 的逆元和 $a^{-im}$ 。

如果不是很懂怎么写 $BSGS$ 的,可以看这里: $Link$

以下是完整版代码:


#include <map>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <unordered_map>

#define ll long long

using namespace std ; 
unordered_map<ll, int> H ;
int N, M, P, ans ; // N ^x = M (mod P)

inline ll gcd(ll a, ll b){
    if (!b) return a ;
    return gcd(b, a % b) ;
}
inline ll expow(ll a, ll b, ll mod){
    ll res = 1 ;
    while (b) res = ((b & 1)?res * a % mod : res), a = a * a % mod, b >>= 1 ;
    return res ;
}
inline ll exgcd(ll &x, ll &y, ll a, ll b){
    if (!b){ x = 1, y = 0 ; return a ; }
    ll t = exgcd(y, x, b, a % b) ; y -= x * (a / b) ; return t ;
}
inline ll BSGS(ll a, ll b, ll mod, ll qaq){
    H.clear() ; ll Q, p = ceil(sqrt(mod)), x, y ; 
    exgcd(x, y, qaq, mod), b = (b * x % mod + mod) % mod, 
    Q = expow(a, p, mod), exgcd(x, y, Q, mod), Q = (x % mod + mod) % mod ;
    for (ll i = 1, j = 0 ; j <= p ; ++ j, i = i * a % mod)  if (!H.count(i)) H[i] = j ;
    for (ll i = b, j = 0 ; j <= p ; ++ j, i = i * Q % mod)  if (H[i]) return j * p + H[i] ; return -1 ;
}
inline ll exBSGS(){
    ll qaq = 1 ;
    ll k = 0, qwq = 1 ; 
    if (M == 1) return 0 ; 
    while ((qwq = gcd(N, P)) > 1){
        if (M % qwq) return -1 ;
        ++ k, M /= qwq, P /= qwq, qaq = qaq * (N / qwq) % P ;
        if (qaq == M) return k ;
    }
    return (qwq = BSGS(N, M, P, qaq)) == -1 ? -1 : qwq + k ;
}                    
int main(){
    while(cin >> N){
        scanf("%d%d", &P, &M); if (!N && !M && !P) return 0 ;
        N %= P, M %= P, ans = exBSGS() ; if (ans < 0) puts("No Solution") ; else cout << ans << '\n' ;
    }
}