搜索结果
查询Tags标签： 原根，共有 7条记录-
阶 原根 离散对数
阶 原根 离散对数 阶 定义 \(a\mod p\) 的阶是 \(a^e\equiv1\pmod p\) 的最小指数 \(e\) 符号语言: \(\delta_p(a)\) 代表 \(a\) 在 \(\mod p\) 的意义下的最小指数 \(e\) 使\(a^e\equiv1\pmod p\)根据这个表格，我们可以举出一些例子\[\delta_5(1) = 1~~~\delta_7(4) = 3…
2023/6/6 1:22:53 人评论 次浏览 -
[笔记] 求质数的原根
素数的原根的定义：若\(g^0,g^1 \cdots g^{p-1}\)在mod p意义下各不相同，则g是p的一个原根。质数的最小的原根通常很小，所以从2开始枚举每一个正整数，判断其是否为p的原根。 判断的方法：如果g不是p的原根，则存在\(0\leq i < j \leq p-1\)满足\(g^i≡g^j\)(mod p)，…
2022/7/8 23:23:37 人评论 次浏览 -
原根和循环卷积 2016国家集训队论文集—再探快速傅里叶变换
原根和循环卷积\(\ \ \ 2016\)国家集训队论文集—再探快速傅里叶变换 这个连原根都不明白的屑来补坑了原根 阶\(:\) 设\(m>1,\gcd(a,m)=1,\)那么最小的\(r\)满足\(a^r=1(\mod m)\)称为\(r\)是\(a\)在\(\mod m\)意义下的阶,记为\(\delta_m(a)\) 有关定理\(:\) \(1.\)若\…
2022/3/27 23:26:50 人评论 次浏览 -
#原根，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 人评论 次浏览 -
Codeforces 360D - Levko and Sets（数论+原根）
Codeforces 题面传送门 & 洛谷题面传送门 首先考虑对于一个 \(x\)，什么样的数能够在 \(x\) 对应的集合中表示出来，不难发现一个数 \(y\) 属于 \(x\) 对应的集合，当且仅当其可以写成 \(x^{c_1b_1+c_2b_2+\cdots+c_mb_m}\) 的形式，而由于 \(p\) 是质数，根据费马小定…
2022/1/28 6:08:49 人评论 次浏览 -
CSP 后多校十一(多项式、原根待补)
NOIP2018 感觉不是很难，一开始想的是二分最多能选多少个物品，然后一元二次函数直接 \(O(1)\) 出结果. 但是被卡精度了，其实只用二分每个物品最多花多少钱，画两个一元二次函数就行了. 因为两个物品的花费越接近越优，于是就完了. CSP 2019 多项式不会. CSP 2020 考场上…
2021/11/10 6:39:47 人评论 次浏览 -
CSP 后多校十一(多项式、原根待补)
NOIP2018 感觉不是很难，一开始想的是二分最多能选多少个物品，然后一元二次函数直接 \(O(1)\) 出结果. 但是被卡精度了，其实只用二分每个物品最多花多少钱，画两个一元二次函数就行了. 因为两个物品的花费越接近越优，于是就完了. CSP 2019 多项式不会. CSP 2020 考场上…
2021/11/10 6:39:47 人评论 次浏览
