搜索结果
查询Tags标签： equiv，共有 29条记录-
Millar-Rabin 米勒罗宾算法小结 （内附费马小定理证明以及二次探测定理证明）
因为他我学了龟速乘 Millar-robin 米勒罗宾 这个小东西是用来素数判定的，且听我细细道来。 前置知识肥妈小定理 又名费马小定理 ： 当一个数 \(x\) 不是一个质数 \(p\) 的倍数时有： \[x^{p-1} \equiv 1 \pmod{p} \]证明： 对于一个序列 \[b = \left \{1,2,3....p-1\rig…
2022/9/2 1:25:35 人评论 次浏览 -
关于一加一碰手游戏的一点研究
首先介绍 “一加一碰手游戏”。 具体规则是这样的：游戏有两个玩家，每个玩家有两只手。初始所有手上的数字都为 \(1\)。两个玩家轮流行动，轮到一个玩家时他可以选择对方任意一只手上的数字，将自己任意一只手上的数字加上这个数后对 \(10\) 取余数。若有一只手上的数字为…
2022/8/29 23:25:46 人评论 次浏览 -
快速幂求逆元
快速幂求逆元 给定 $ n $ 组 $ a_i, p_i $，其中 $ p_i $ 是质数，求 $ a_i $ 模 $ p_i $ 的乘法逆元，若逆元不存在则输出 impossible。 注意：请返回在 $ 0 \sim p-1 $ 之间的逆元。 乘法逆元的定义若整数 $ b，m $ 互质，并且对于任意的整数 $ a $，如果满足 $ b|a $，…
2022/7/24 6:23:50 人评论 次浏览 -
Baby_Step_Gaint_Step(BSGS) 算法
\(BSGS\) 算法，又称 “北（\(B\)）上（\(S\)）广（\(G\)）深（\(S\)）” 算法，“拔山盖世”算法，可以在 \(O(\sqrt{n})\) 的复杂度内求解离散对数问题。题目描述： 给定质数 \(p\) 和整数 \(a, n\)，求最小的非负整数 \(m\) ，满足 \(a^m \equiv n(mod\ \ p)\) 。 算法…
2022/7/21 1:23:35 人评论 次浏览 -
RSA
一、基本原理 公钥与私钥的产生随机选择两个不同大质数 \(p\) 和 \(q\)，计算 \(n=p\times q\)。 求得 \(\varphi ( n )\)。 选择 \(e < \varphi ( n )\)，使 $e \perp \varphi (n) $。并求得 \(e\) 在模 \(\varphi ( n )\) 下的逆元 \(d\)。 销毁 \(p\) 和 \(q\)。此时…
2022/6/24 23:24:40 人评论 次浏览 -
算法灵魂源自数学--数论数学笔记
数论数学笔记第一章：整数的可除性整除的概念及欧几里得除法整除定义 素数与合数的定义 不完全商和余数定义最大公因数与广义欧几里得除法最大公因数 最大公因数性质整除的进一步性质及最小公倍数最小公倍数 素数分解 素数定理同余式同余的概论和及基本性质同余定义剩余类…
2022/5/30 1:21:05 人评论 次浏览 -
中国剩余定理
中国剩余定理 在同余方程得以解决之后，设想有一个这样的问题： \[\begin{cases}x\equiv a_1\pmod{m_1}\\x\equiv a_2\pmod{m_2}\\\cdots\\x\equiv a_n\pmod{m_n}\end{cases} \]\(2\le n\le 10\) , \(0\le a_i<m_i\le 10^5\) , \(1\le \prod m_i\le 10^{18}\) , 对于 \…
2022/5/29 23:20:36 人评论 次浏览 -
乘法逆元学习笔记
乘法逆元和求法 基本的数论知识，有必要补一发。 开始之前模运算：取余运算，比如 \(a \bmod b\) 就是 \(a\) 除以 \(b\) 得到的余数。性质：在加、减、乘、乘方的运算过程中，进行取余运算，不会对结果产生影响。优先级：取余运算的优先级和乘法、除法的优先级相同，高于…
2022/4/30 23:14:13 人评论 次浏览 -
【Coel.做题笔记】【旁观者…】二次剩余- Cipolla 算法
题前闲语 这周末就是省选了，甚至考场就在这个机房，可惜我并没有参加的机会。 唉，今年得好好努力了！ 题目简介 给出 \(N,p\)，求解方程 \[x^2 \equiv N(\bmod ~p) \]多组数据。 保证 \(p\) 是奇素数。 输入输出格式 输入格式第一行一个整数 $T$ 表示数据组数。 接下来 …
2022/4/14 20:12:43 人评论 次浏览 -
中国剩余定理
简介 中国剩余定理 (Chinese Remainder Theorem, CRT) 可求解如下形式的一元线性同余方程组（其中\(m_1,m_2,...,m_k\) 互质） \[\left\{\begin{array}{ccc} {x} & {\equiv} & {a_{1}\left(\bmod \ m_{1}\right)} \\ {x} & {\equiv} & {a_{2}\left(\bmod …
2022/4/11 23:13:37 人评论 次浏览 -
【学习笔记】BSGS 算法
引入 BSGS（baby-step giant-step），即大步小步算法，常用于求解离散对数问题。该算法可以在 \(O(\sqrt p)\) 的时间复杂度内求解 \[a^x \equiv b \pmod p \]第一部分：\(a \perp p\) 我们将求解的答案 \(x\) 设为 \(km-c \ (c < m)\) 的形式，即 \[a^{km-c} \equiv b…
2022/3/5 22:15:11 人评论 次浏览 -
【记录】妙妙题
新坑。 arc136 e \(1\) 到 \(n\) 的数，如果两个数不互质则从小到大连有向边，点带权，求一个权最大点集使没有互相可达的点。sol 首先把 $1$ 选掉，考虑两个数 $x,y$ 互相可达的条件：\(x\equiv 0,y\equiv 0\) 一定可达。 \(x\equiv 1,y\equiv 0\) 则 \(x+minprime_x \le…
2022/3/4 23:45:22 人评论 次浏览 -
#原根，BSGS，扩欧#51nod 1038 X^A Mod P
题目 \(T(T\leq 100)\) 组询问在模 \(P\) 意义下给 \(B\) 开 \(A\) 次方根， 求出 \([0,P)\) 的所有解，\(P\) 是一个质数。分析 求出 \(P\) 的原根 \(G\)，若 \(G^x\equiv B\pmod{P}\)，这个 \(x\) 可以通过 BSGS 求出来。 那么 \(X^A\equiv B\pmod{P}\) 就可以转换成 \(…
2022/2/18 23:22:25 人评论 次浏览 -
同余
定义： 若\((a-b)\ mod\ p=0\)，则\(a\)与\(b\)在模\(p\)的意义下同余，记作\(a\equiv b(mod\ p)\)。(\(a,c\in Z\)(整数)，\(m\in N^*\)(正整数)) 性质： 1.\(a\equiv a(mod\ p)\) 2.若\(a\equiv b(mod\ p)\)，则\(b\equiv a(mod\ p)\) 3.若\(a\equiv b(mod\ p)\)，且\(b…
2022/2/18 23:19:07 人评论 次浏览 -
数论同余学习笔记 Part 2
逆元 准确地说，这里讲的是模意义下的乘法逆元。 定义：如果有同余方程 \(ax\equiv 1\pmod p\)，则 \(x\) 称为 \(a\bmod p\) 的逆元，记作 \(a^{-1}\)。 作用是抵消乘法，即 \(x\cdot a\cdot a^{-1}\equiv x\pmod p\) 进一步可以得到 \(\frac xa\equiv x\times a^{-1}\pm…
2022/2/8 23:51:17 人评论 次浏览
