「学习笔记」BSGS

「学习笔记」BSGS

点击查看目录

Baby-step Giant-step

问题

\(O(\sqrt{p})\) 的时间内求解

\[a^x \equiv b \pmod p
\]

其中 \(a\perp p\),方程的解 \(x\) 满足 \(0 \le x < p\)

算法

首先根据费马小定理 \(a^{p-1}\equiv1\pmod{p}\),不难发现 \(1\sim p-1\) 是一个循环节,也就是说只用判断 \(1\sim p-1\) 这些数里是否存在一个方程的解 \(x\) 即可。

但是这个范围仍然很大,直接 \(O(p)\) 跑肯定不行。

\(x=A\left\lceil\sqrt{p}\right\rceil-B (0\le A, B\le\left\lceil\sqrt{p}\right\rceil)\),则 \(a^{A\left\lceil\sqrt{p}\right\rceil-B} \equiv b \pmod p\)

\(a^{A\left\lceil\sqrt{p}\right\rceil} \equiv a^{B} b \pmod p\)

由于 \(A,B\) 不大,我们可以枚举出所有 \(a^{B} b\)\(a^{A\left\lceil\sqrt{p}\right\rceil}\) 的取值。用 map 存下所有 \(a^{B} b\) 的取值,再查找 \(a^{A\left\lceil\sqrt{p}\right\rceil}\) 的取值是否出现过即可。

注意在求出满足 \(a^{A\left\lceil\sqrt{p}\right\rceil} \equiv a^{B} b \pmod p\) 的合法 \(A,B\) 后还要推回到 \(a^{A\left\lceil\sqrt{p}\right\rceil-B} \equiv b \pmod p\) 才能得到解 \(x=A\left\lceil\sqrt{p}\right\rceil-B (0\le A, B\le\left\lceil\sqrt{p}\right\rceil)\),这一步要求 \(a\perp p\),但不要求 \(p\in\mathbb{P}\)

时间复杂度:\(O(\sqrt{p}\log_2\sqrt{p})\)

你想更快的话你用哈希表也行。

例题

Discrete Logging

板子题,放一份代码。

代码

点击查看代码
inline ll FastPow (ll a, ll b, ll P) {
	ll ans = 1;
	while (b) {
		if (b & 1) ans = ans * a % P;
		a = a * a % P, b >>= 1;
	}
	return ans;
}
inline void Solve () {
	ll qp = ceil (sqrt (p));
	_for (i, 0, qp) h[n * FastPow (b, i, p) % p] = i;
	ll t = FastPow (b, qp, p), num = 1;
	_for (i, 1, qp) {
		num = num * t % p;
		if (h[num]) {
			ans = (i * qp % p - h[num] + p) % p;
			return;
		}
	}
	return;
}

P3306 [SDOI2013] 随机数生成器

思路

推式子题。

\[\begin{aligned}
x_{i}
&\equiv x_{i-1}a+b \pmod{p}\\
&\equiv (x_{i-2}a+b)a+b \pmod{p}\\
&\equiv x_{i-2}a^2+ab+b \pmod{p}\\
&\equiv (x_{i-3}a+b)a^2+ab+b \pmod{p}\\
&\equiv x_{i-3}a^3+a^2b+ab+b \pmod{p}\\
&\equiv x_{1}a^{i-1}+b(\sum_{k=0}^{i-2}a^{k}) \pmod{p}\\
&\equiv x_{1}a^{i-1}+b\frac{1-a^{i-2}}{1-a} \pmod{p}\\
\end{aligned}
\]

那么:

\[\begin{aligned}
x_{1}a^{i-1}+b\frac{a^{i-1}-1}{a-1} &\equiv t \pmod{p}\\
x_{1}a^{i-1}+\frac{a^{i-1}b}{a-1} - \frac{b}{a-1} &\equiv t \pmod{p}\\
a^{i-1}(x_{1}+\frac{b}{a-1}) &\equiv t + \frac{b}{a-1} \pmod{p}\\
a^{i-1} &\equiv \frac{t + \frac{b}{a-1}}{x_{1}+\frac{b}{a-1}} \pmod{p}\\
\end{aligned}
\]

\(i - 1 = A \left \lceil \sqrt p \right \rceil - B\),则 \(a^{A \left \lceil \sqrt p \right \rceil - B} \equiv \dfrac{t + \frac{b}{a-1}}{x_{1}+\frac{b}{a-1}} \pmod{p}\)

则:

\[\begin{aligned}
a^{A \left \lceil \sqrt p \right \rceil} &\equiv a^{B}\dfrac{t + \frac{b}{a-1}}{x_{1}+\frac{b}{a-1}} \pmod{p}
\end{aligned}
\]

就可以跑 BSGS 了。

但是还有几个细节:

  • \(x1=t\):答案为 \(1\)
  • \(a=0\):如果 \(b=t\),答案为 \(2\),否则为 \(-1\)
  • \(a=1\):此时 \(x_i=x_1+(i-1)b\),算逆元即可。

P2485 [SDOI2011]计算器

思路

是不是再来一个 CRT 就同余全家桶了。

裸的逆元和 BSGS,但是题目只保证 \(p\in\mathbb{P}\) 不保证 \(y\perp p\),需要特判一下 \(p\) 是否为 \(y\) 的倍数。

if (!y) { ans = (z % p ? -1 : 1); return; }

Matrix

思路

定义一个矩阵的类然后直接跑就行,感觉没啥大区别。

代码

点击查看代码
const ll N = 110;
namespace SOLVE {
	ll n, p, ans;
	class Matrix {
	public:
		ll len, m, ma[N][N];
		inline void Init (ll l, ll md) {
			len = l, m = md;
			memset (ma, 0, sizeof (ma));
			_for (i, 1, l) ma[i][i] = 1;
			return;
		}
		inline void Print () {
			_for (i, 1, n) {
				_for (j, 1, n) {
					printf ("%lld ", ma[i][j]);
				}
				puts ("");
			}
			puts ("");
			return;
		}

		ll* operator [] (ll x) { return ma[x]; }
		Matrix operator * (Matrix another) const {
			Matrix ans;
			ans.Init (len, m);
			memset (ans.ma, 0, sizeof (ans.ma));
			_for (i, 1, len) _for (j, 1, len) _for (k, 1, len)
				ans[i][j] = (ans[i][j] + ma[i][k] * another[k][j] % m) % m;
			return ans;
		}
		bool operator == (Matrix another) const {
			_for (i, 1, n) _for (j, 1, n) if (ma[i][j] != another[i][j]) return 0;
			return 1;
		}
		bool operator < (Matrix another) const {
			_for (i, 1, len) _for (j, 1, len) {
				if (ma[i][j] < another[i][j]) return 1;
				if (ma[i][j] > another[i][j]) return 0;
			}
			return 0;
		}
	} a, b;
	std::map <Matrix, ll> mp;

	inline ll rnt () {
		ll x = 0, w = 1; char c = getchar ();
		while (!isdigit (c)) { if (c == '-') w = -1; c = getchar (); }
		while (isdigit (c)) x = (x << 3) + (x << 1) + (c ^ 48), c = getchar ();
		return x * w;
	}

	inline Matrix FastPow (Matrix a, ll b, ll P) {
		Matrix ans;
		ans.Init (n, P);
		while (b) {
			if (b & 1) ans = ans * a;
			a = a * a, b >>= 1;
		}
		return ans;
	}

	inline void In () {
		n = rnt (), p = rnt ();
		a.Init (n, p), b.Init (n, p);
		_for (i, 1, n) _for (j, 1, n) a[i][j] = rnt ();
		_for (i, 1, n) _for (j, 1, n) b[i][j] = rnt ();
		return;
	}
	inline void Solve () {
		ll qp = ceil (sqrt (p));
		_for (i, 0, qp) mp[b] = i, b = b * a;
		a = FastPow (a, qp, p);
		Matrix mat; mat.Init (n, p);
		_for (i, 1, qp) {
			mat = mat * a;
			if (mp[mat]) {
				ans = (i * qp % p - mp[mat] + p) % p;
				return;
			}
		}
		return;
	}
	inline void Out () {
		printf ("%lld\n", ans);
		return;
	}
}

原文链接:https://www.cnblogs.com/Keven-He/p/BabyStepGiantStep.html

本站文章如无特殊说明,均为本站原创,如若转载,请注明出处:「学习笔记」BSGS - Python技术站

(0)
上一篇 2023年4月17日
下一篇 2023年4月17日

相关文章

  • Python语言实现二分法查找

    Python语言实现二分法查找 二分法查找是一种常见的查找算法,它可以在有序数组中快速查找目标元素。本文将介绍如何使用Python语言实现二分法查找。 1. 算法原理 二分法查找的基本思想是:将有序数组分成两部分,取中间元素与目标元素进行比较,相等则返回中间元素的下标,如果目标元素小于中间元素,则在左半部分继续查找,否则在右半部分继续查找,直到找到目标元素或…

    python 2023年5月14日
    00
  • 最小二乘法及其python实现详解

    下面是详细讲解“最小二乘法及其Python实现详解”的完整攻略。 最小二乘法 最小二乘法是一种常用的回归分析方法,用于拟合数据点与数学模型之间的关系。该方法的核心思想是通过最小化数据点与拟合曲线之间的距离,来确定最佳拟合曲线的参数。 下面是一个Python实现最小二乘法的示例: import numpy as np def least_squares(x, …

    python 2023年5月14日
    00
  • JS数据结构之队列结构详解

    JS数据结构之队列结构详解 什么是队列结构? 队列结构是一种遵循先进先出(FIFO)原则的线性数据结构,它可以用来存储一系列待处理的数据,其中队首是最先进入队列的元素,队尾是最后进入队列的元素。 在队列中,添加元素的操作叫做enqueue,移除元素的操作叫做dequeue。同时,队列还包括peek方法,查看队列头的元素,以及isEmpty方法,判断队列是否为…

    数据结构 2023年5月17日
    00
  • [Week 19]每日一题(C++,数学,并查集,动态规划)

    目录 [Daimayuan] T1 倒数第n个字符串(C++,进制) 输入格式 输出格式 样例输入 样例输出 解题思路 [Daimayuan] T2 排队(C++,并查集) 输入格式 输出格式 样例输入1 样例输出1 样例输入2 样例输出2 样例输入3 样例输出3 数据规模 解题思路 [Daimayuan] T3 素数之欢(C++,BFS) 数据规模 输入格…

    算法与数据结构 2023年5月4日
    00
  • python机器学习之KNN分类算法

    Python机器学习之KNN分类算法 KNN(K-Nearest Neighbors)是一种基本的分类算法,它的基本思想是:如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别,则该样本也属于这个类别。 KNN算法流程 KNN算法的流程如下: 计算测试样本与训练样本之间的距离; 选取距离最近的k个训练样本; 统计k个训练样…

    python 2023年5月14日
    00
  • 详解最小生成树原理与使用方法

    最小生成树简介 最小生成树(Minimum Spanning Tree, MST)是一种在带权无向连通图中求解最小边权和的树形图的算法。最小生成树可以用来解决许多实际问题,例如:电力公司要在多个城市之间铺设电线,银行要在多个城市之间建立银行分行等问题。 最小生成树问题的求解思路有两种,一种是使用Kruskal算法(克鲁斯卡尔算法),一种是使用Prim算法(普…

    算法 2023年3月27日
    00
  • C++深入分析讲解链表

    C++深入分析讲解链表 链表概述 链表是数据结构中最基本和重要的一种,它的实现可以分为链表的节点和链表的指针。每个节点都记录着链表中的一个元素,并带有一个指向下一个节点的指针,这样就可以通过遍历指针,达到遍历链表的目的。 链表数据结构 在C++中,链表可以通过结构体或者类来实现,比如以下这个结构体实现的单向链表: struct Node { int data…

    数据结构 2023年5月17日
    00
  • Java面试题冲刺第十三天–数据库(3)

    当我们准备面试数据库相关的职位时,需要掌握SQL语言和常见的数据库管理系统。下面是针对Java面试中可能出现的常见数据库面试题的一些攻略。 1. 数据库连接的常见方式 在Java中,要与数据库连接有两种方式:JDBC和ORM框架。 (1) JDBC JDBC是Java连接数据库的标准方式,使用JDBC可以通过Java程序来连接不同的数据库。连接数据库的步骤包…

    数据结构 2023年5月17日
    00
合作推广
合作推广
分享本页
返回顶部