BSGS&exBSGS | 王大神—

题解模板数论欧拉函数费马小定理扩展欧几里得算法 BSGS exBSGS 快速幂

Markdown

发布日期: 2021-12-28

更新日期: 2021-12-28

文章字数: 1.7k

阅读次数:

BSGS

P3846 可爱的质数/【模板】BSGS

题目让我们求：

$k^x\equiv n(\mod p)$

如果存在 $x$ 输出，否则输出：no solution。

$\because x^{p-1}\equiv1(\mod p)$ $\because x^0\equiv1(\mod p)$

那么如果，$\exists x,x\in[0,p-1]$。

那么就可以暴力找 $x$，但是根据数据范围会发现，会超时，那么就要想办法找优化。

BSGS 最精妙的地方在于它构造了一个数：$m=\lceil{\sqrt{p}}\rceil$。

为什么这么说呢？我们将 $x$ 换一种写法：$x=a\times m-b$。那么就有：

$k^{a\times m-b}\equiv 1(\mod p)$ $k^{a\times m}\equiv k^{b} (\mod p)$ $(k^m)^a\equiv k^b(\mod p)$

注意题目恒等式的右边还有一个常数 $n$：

$(k^m)^a\equiv n\times k^b(\mod p)$

这时，暴力枚举 $b$，用 map 或其他存储方式记录值。在枚举 $a$，如果匹配上了，通过 $a\times m-b=x$ 求出结果即可。

此时，由于 $m=\lceil{\sqrt{p}}\rceil,x < p$，所以 $a < \sqrt{p}$。

如果 $b\ge \sqrt{p}$，假设 $b=d\times \sqrt{p}+c$ 那么我们完全可以当成 $m\times(a-d)-c$ 的情况处理，而这种情况包含在了 $a$ 枚举的区间，所以 $b\in[0,\sqrt{p})$。

复杂度就将到了 $O(\sqrt{p})$。

注意：在枚举的时候先枚举右边，记录结果，这样左边从小到大枚举的时候如果匹配直接返回的值保证最小。

代码

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
#include<map> 
using namespace std;
long long r_r(){//快读 
  long long k=0,f=1;
  char c=getchar();
  while(!isdigit(c)){
    if(c=='-')f=-1;
    c=getchar();
  }
  while(isdigit(c)){
    k=(k<<1)+(k<<3)+(c^48);
    c=getchar(); 
  }
  return k*f;
}
const int o_o=1e6+10;
map<int,int> h_h;//记录得到的值 
long long k_m(long long a,long long b,long long p){//快速幂 
  long long r_s=1;
  while(b){
    if(b&1)r_s=(r_s*a)%p;
    a=(a*a)%p;
    b>>=1;
  }
  return r_s;
}
long long b_g(long long a,long long b,long long p){
  int s_z=ceil(sqrt(p)); 
  long long b_s=b%p;
  h_h[b_s]=0;
  for(int i=1;i<=s_z;i++){//枚举，记录得到的情况 
    b_s=b_s*a%p;
    h_h[b_s]=i;//记录 
  }
  b_s=k_m(a,s_z,p);//一次幂 
  long long t_p=1;
  for(long long i=1;i<=s_z;i++){//枚举，尝试匹配 
    t_p=t_p*b_s%p;
    if(h_h[t_p])//标记过，匹配成功 
      return ((i*s_z-h_h[t_p])%p+p)%p;//返回值 
  }
  return -1;//未找到 
}
long long p=r_r(),b=r_r(),n=r_r();
int main(){
  if(!(b%p)){
    if(n==0){//可以整除，最小值 1 
      puts("1");
      return 0;
    }else if(n==1){//只能是 0 
      puts("0");
      return 0;
    }
        puts("no solution");//其他情况无解 
        return 0;
    }
  long long a_s=b_g(b,n,p);//找最小值 
  if(a_s!=-1) printf("%lld",a_s);//找到 
  else puts("no solution");//未找到 
  return 0;
}

扩展 BSGS

P4195 【模板】扩展 BSGS/exBSGS

$k^x\equiv b(\mod p)$

现在 $p$ 不一定是质数了，首先我们要将式子进行一些处理，让 $p$ 和 $k$ 互质，这样就可以正常使用 BSGS 计算结果了。

恒等式除公因数：

$\frac{k^x}{\gcd(k,p)}\equiv\frac{b}{\gcd(k,p)}(\mod \frac{p}{\gcd(k,p)})$

所以我们可以先将 $k^x$ 和 $p$ 化简，使他们互质。（如果 $b\not=0,1$ 并且 $b\nmid \gcd(k,p)$ 那么无解。）

假设 $k^x$ 每次和 $p$ 的公因数是 $p_i$，一共化简 $n$ 次，那么最后化简为：

$\frac{k^n}{\prod_{i=1}^n}\times k^{x-n}\equiv\frac{b}{\prod_{i=1}^n}(\mod \frac{p}{\prod_{i=1}^n})$

我们可以利用扩展欧几里得（或者费马小定理）求逆元，将 $\frac{k^n}{\prod^n_{i=1}}$ 挪到右边。

$k^{x-n}\equiv(\frac{k^n}{\prod_{i=1}^n})^{-1}\times \frac{b}{\prod_{i=1}^n}(\mod \frac{p}{\prod_{i=1}^n})$

此时的 $k^{x-n}$ 和模数互质，这个形式和 BSGS 的形式相同：

$k^{i\times m-j}\equiv b(\mod p)$ $(k^m)^i\equiv b\times k^{j}(\mod p)$

仍然是枚举右边，同样右边有一个常数。然后从小到大枚举左边，判读是否出现过即可。

注意：此时计算出的是 $i\times m-j=x-n$ 最后要将 $n$ 加回来，才是最后的结果。

代码思路

读入基本信息（注意读入终止条件）。
将数余模数化成互质的情况（同时判断无解和同余是 $1,0$ 的特殊情况）。
计算逆元，将左边化简的一部分挪到右边。
BSGS 枚举情况，有值记录（从小到大枚举保证最小值）返回输出，没有值判无解。

代码

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#include<stack>
#include<map> 
#include<unordered_map>
using namespace std;
long long r_r(){//快读 
  long long k=0,f=1;
  char c=getchar();
  while(!isdigit(c)){
    if(c=='-')f=-1;
    c=getchar();
  }
  while(isdigit(c)){
    k=(k<<1)+(k<<3)+(c^48);
    c=getchar(); 
  }
  return k*f;
}
const long long o_o=1e6+10;

//扩展欧几里得 ax+by=gcd(a,b) 的一组解 
//计算逆元 
long long e_g(long long a,long long b,long long &x,long long &y){
  if(!b){
    x=1;
    y=0;
    return a;
  }
  long long g_d=e_g(b,a%b,y,x);
  y-=(a/b)*x;
  return g_d;
}
long long e_b(long long a,long long b,long long m_d){//扩展 BSGS 
  b%=m_d;
  if(b==1||m_d==1)return 0;//特判 
  long long m_g=0;//统计式 a 和模数互质的幂次 
  long long v_l=1;//a 的 m_g 次幂 
  while(1){
    long long x,y;
    long long d=e_g(a,m_d,x,y);//找到 a 和模数的最大公因数 
    if(d==1)break;//a 和模数互质 
    if(b%d) return -1;//b 不整除公因数，无解 
    
    //去除最小公因数（化简） 
    b/=d;
    m_d/=d;
    v_l=v_l*a/d%m_d;//累计值 
    m_g++;//统计次幂 
    if(b==v_l)return m_g;//已经匹配上，直接返回值即可 
  }
  
  //将处理公因数的部分放到右边 
  long long x,y;
  e_g(v_l,m_d,x,y);//计算逆元 
  x=(x%m_d+m_d)%m_d;//值的逆元“化简” 
  b=b*x%m_d;//右边累计 
  a%=m_d;
  
  //BSGS 操作 
  unordered_map<long long,long long>m_p;
  long long m=ceil(sqrt(m_d));
  long long k_b=1;//恒等右边的值 
  for(int i=0;i<m;i++){
    m_p[b*k_b%m_d]=i;//记录（注意这里同余的不是 1，是 b） 
    k_b=k_b*a%m_d;//枚举所有情况 
  }
  long long k_a=1;//恒等左边的值
  //此时的 k_b 正好是 a 的 m 次幂，直接用即可 
  for(long long i=1;i<=m;i++){
    k_a=k_a*k_b%m_d;//累计 
    if(m_p.count(k_a))return i*m-m_p[k_a]+m_g;//碰到之前枚举过的情况 
    //记得同时累计前面记过的幂，将 a 和模数互质的次数 
  }
  return -1;//没找到，没有答案 
}
int main(){
  long long a=r_r(),p=r_r(),b=r_r();//读入输入 
  while(a||b||p){//结束标志全 0 
    long long a_s=e_b(a,b,p);//查询结果 
    if(a_s==-1) puts("No Solution");//无解 
    else printf("%lld\n",a_s);
    a=r_r(),p=r_r(),b=r_r();//下一组数据 
  }
  return 0;
}