数论笔记
310 字
2 分钟
数论笔记
随便写点数论~
数论基础略过
二次剩余
对于 ,若存在整数 使得
则 为模 的二次剩余,否则为二次非剩余
Euler 判别法
根据费马小定理,二次剩余的一个简单的判据就是考察 是 还是
就说明是二次剩余, 就说明是二次非剩余
这被称为Euler 判别法,当然 另说
证明
应该没伪证吧
最直接就考虑费马小定理
也就是
要么是 要么是
而对于一个二次剩余 ,
则
满足 的 至多 个
而二次剩余本身恰好 个
于是
二次剩余求解
很巧妙的一点就是,对于 型的 的二次剩余模 下的平方根是容易求得的
然后 型的就用到一种 Tonelli-Shanks 这个迭代逼近的算法,
em,查阅发现在算法竞赛中似乎 Cipolla 用的更多?
合数模二次剩余似乎比较困难,约等于质因数分解这样子
咕咕咕
文章分享
如果这篇文章对你有帮助,欢迎分享给更多人!
相关文章智能推荐
1
根号分治
算法2026-11-16
2
2026 CCPC 长春 游记
竞赛第一次ccpc qwq
3
第二十四届电子科技大学 ACM-ICPC 程序设计竞赛 初赛游记
竞赛第一次校赛qwq
4
Hexo 博客搭建教程
工程从零开始的个人博客搭建!
随机文章随机推荐
评论区
正在加载 Twikoo…
正在加载 Giscus…









