「学习笔记」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
  • 2020滴滴最新PHP试题(附答案及解析)

    题目链接:https://www.fibar.cn/newsDetail/18216.html 本文主要是对“2020滴滴最新PHP试题(附答案及解析)”的解题思路和过程进行详细讲解。 题目难度 此题属于中等难度,需要考生具备 PHP 基础知识和算法基础。 题目要求 题目要求我们编写一个程序,实现多个字符串的排序输出。程序需要满足以下要求: 输入:多个字符串…

    数据结构 2023年5月17日
    00
  • 详解最短路径算法原理与使用方法

    最短路径算法是用于寻找图中两点之间最短路径的算法,经常出现在网络路由、地图路径规划、货运调度等应用场景中。常见的最短路径算法包括Dijkstra算法、Bellman-Ford算法、Floyd算法等。 本文将围绕Dijkstra算法展开详细讲解。Dijkstra算法是一种单源最短路径算法,也就是给定起点,通过贪心策略逐步扩展路径,直到找到目标节点为止。 算法流…

    算法 2023年3月27日
    00
  • Python数据结构之二叉排序树的定义、查找、插入、构造、删除

    Python数据结构之二叉排序树 一、定义 二叉排序树(Binary Search Tree,BST),也称为二叉查找树或二叉搜索树,是一种基于二叉树的数据结构,其中每个节点都包含一个键值,且满足: 左子树中所有节点的键值均小于当前节点; 右子树中所有节点的键值均大于当前节点; 这是一种自平衡的数据结构,可以快速地进行查找、插入、删除等操作。 二、查找 查找…

    数据结构 2023年5月17日
    00
  • C语言结构体struct详解

    C语言结构体struct详解 什么是结构体? 在C语言中,结构体是一种用户自定义的数据类型,它可以将不同的数据类型组合在一起形成一个新的数据类型。结构体主要由结构体名、成员和符号构成。 使用结构体可以方便地定义一些复杂的数据类型,例如表示一个学生信息的数据类型,可以包括姓名、学号、性别、年龄等信息。 结构体的定义和声明 结构体的定义通常放在函数外部,以便在整…

    数据结构 2023年5月17日
    00
  • python人工智能深度学习算法优化

    下面是详细讲解“Python人工智能深度学习算法优化”的完整攻略,包括算法优化方法、Python实现和两个示例。 算法优化方法 深度学习算法优化是通过改进算法的训练过程,提高模型的性能和泛化能力。常见的深度学习算法优化方法包括以下几种: 1. 正则化 正则化是一种常用的深度学习算法优化方法,其主要思想是对模型参数进行约束,避免模型过拟合。常见的正则化方法包括…

    python 2023年5月14日
    00
  • Java数据结构之HashMap和HashSet

    Java数据结构之HashMap和HashSet HashMap 介绍 HashMap是一种基于哈希表实现的Map集合,它提供了快速的插入、查询、删除操作。HashMap中存储的元素是以键值对(Key-Value)的形式存储的,其中Key是用来从Map中查找值的索引,Value是存储在Map中的值。HashMap中的Key和Value都可以为null,但是在…

    数据结构 2023年5月17日
    00
  • python算法学习之计数排序实例

    Python算法学习之计数排序实例 计数排序是一种非比较排序算法,它的时间复杂度为O(n+k),其中n是待排序元素的个数,k是元素的取值范围。计数排序的基本思想是对于给定的输入序列中的每元素x,确定该序列中值小于x的元素的个数,然后将x直接存放到相应的输出序列的位置。计数排序的核心在于将输入的数据值转化为键存储在额外开的数组空间中。作为一种线性时间杂度的排序…

    python 2023年5月14日
    00
合作推广
合作推广
分享本页
返回顶部