搜索结果
查询Tags标签： 数论，共有 47条记录-
exgcd 学习笔记
定义 又名扩展欧几里得算法（辗转相除法） 是用来求 \(ax+by=gcd(a,b)\) 中未知数的算法算法证明 拿到一组 \(a,b\) ，设 \(G=gcd(a,b)\) 目标：求出满足 \(ax+by=G（1）\) 的 \(x\) 与 \(y\) 如果 已知一组 \(x2,y2\) ，满足 \(bx2+\) \((a\) \(mod\) \(b)y2=G（2）\) 此…
2023/12/24 18:03:00 人评论 次浏览 -
算法学习笔记(24): 狄利克雷卷积和莫比乌斯反演
狄利克雷卷积和莫比乌斯反演看了《组合数学》，再听了学长讲的……感觉三官被颠覆……目录狄利克雷卷积和莫比乌斯反演狄利克雷卷积 特殊的函数函数之间的关系 除数函数和幂函数 欧拉函数和恒等函数卷积的逆元莫比乌斯函数与莫比乌斯反演 求法 数论分块（整除分块）莫比乌…
2023/6/8 11:53:23 人评论 次浏览 -
阶 原根 离散对数
阶 原根 离散对数 阶 定义 \(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 人评论 次浏览 -
NC17383 A Simple Problem with Integers
题目链接 题目 题目描述 You have N integers A1, A2, ... , AN. You are asked to write a program to receive and execute two kinds of instructions:C a b means performing \(A_i = A_i^2 \mod 2018\) for all Ai such that a ≤ i ≤ b. Q a b means query the sum…
2023/5/1 5:22:04 人评论 次浏览 -
道长的算法笔记：数论基础汇总
质数判定与筛选给定一个正整数 \(N\)，如果存在一个数 \(T\)，T 满足\((2\leq T \leq N -1)\) 则称 \(N\) 是一个合数，如果不存在这样这样的因数 \(T\)，则称\(N\) 质数。简单来说，一个数\(N\) 如何仅能被 \(1\) 与 \(N\) 本身整除，则称这个数字是质数，或称素数(Prime…
2022/9/3 14:25:25 人评论 次浏览 -
数论----同余方程
《贝祖定理》 简单来说是: 整数 a,b ,gcd(a,b)=d; 则 存在x,y使ax+by=d成立 证明： 《扩展欧几里得算法》 由贝祖定理：ax+by=gcd(a,b) 则：当不断取模gcd(a,b)=......=gcd(an,0)时 an*x+b*0=gcd,而an=gcd，所以 x=1,y=任意，为了方便y=0; 设：当前层ax+by=gcd 已知下…
2022/8/23 6:23:52 人评论 次浏览 -
【模板】数论板子
数论分块 用于求解 \[\sum\limits_{i=1}^{n}f_i\cdot \left\lfloor\dfrac{n}{i}\right\rfloor \]亦可求解多维 \[\sum\limits_{i=1}^{\min(n_1,n_2,\cdots,n_k)}(f_i\cdot \prod\limits_{j=1}^{k}\left\lfloor\dfrac{n_j}{i}\right\rfloor) \]前提是求出了数论函数\(f(n)\…
2022/6/7 23:21:17 人评论 次浏览 -
数论补全计划【蒟蒻数论乱证】
写在前面55然而我太逊了所以虎哥讲数论的时候一直把数论的费马小定理什么都都咕着，导致我现在学组合数取模啥都不会，所以就有了这个计划 虎哥写的blog比我写的好多了，而且贼全，我就自己重复证一证加深印象⑧ 虎哥的blog✌ 奇怪怪我不会LATEX。。。那我就这么着打吧 我…
2022/6/3 23:23:18 人评论 次浏览 -
算法灵魂源自数学--数论数学笔记
数论数学笔记第一章：整数的可除性整除的概念及欧几里得除法整除定义 素数与合数的定义 不完全商和余数定义最大公因数与广义欧几里得除法最大公因数 最大公因数性质整除的进一步性质及最小公倍数最小公倍数 素数分解 素数定理同余式同余的概论和及基本性质同余定义剩余类…
2022/5/30 1:21:05 人评论 次浏览 -
数论——素数模的逆（c/c++实现）
素数模的逆 又是可恶的密码学。 每天疯狂求逆，天天辗转相除法，实在是腻了。 因此有了以下代码、、 #include <iostream> #include <vector> #include <cmath> #include <map> using namespace std;int inverse(int x, int mod){// 计算x模mod的…
2022/5/4 14:13:02 人评论 次浏览 -
数论模运算以及快速幂小解
来到数论王国，一切都得重新开始啦 模运算，顾名思义，对一个数进行取模运算，在大数运算中，模运算是常客 如果一个数太大无法直接输出，或者是不需要直接输出，可以对他进行取模缩小数值在输出 我们习惯这样写：a%b=c 取模的结果一般满足于0<=c<=m-1,m一般是题目给…
2022/4/14 23:15:50 人评论 次浏览 -
dls数论课程学习
数论 整除/gcd 一些常见的结论 1-n之间的素数个数：n/lnn 级别的 第n个素数的大小：nlogn级别大小 1-n的倒数和：logn级别 1-n之间素数的倒数和：loglogn级别的a|c, b|c, (a, b) = 1 --> ab|c, a,b分别是c的一些质因子乘积，且a,b没有相同的质因子，所以c%(ab)==0或者…
2022/3/6 23:16:22 人评论 次浏览 -
ADV-1117 超级快速幂（数论）
问题描述给出a,b,c。令p=1000000007, z=b^c, y=a^z, x=y mod p。请求出x。 输入格式三个整数分别是a,b,c 输出格式请输出x 数据规模和约定abc都不超过10^9 思路 不能使用a^(b^c%mod)%mod 考虑费马小定理 当a和p互质时， a ^ (p - 1) % p = 1 最后的结论是a^(b^c) % mod = …
2022/3/4 23:46:53 人评论 次浏览 -
acwing数论笔记
筛法求质数时间复杂度 质数定理:1-n中有n/(lnn)个质数 线性筛
2022/2/23 6:23:42 人评论 次浏览 -
蓝桥杯 第八讲 数论
一、算法 1.欧几里得算法(辗转相除法求最大公约数) int gcd(int a,int b) {return b==0?a:gcd(b,a%b); }辗转相减法（求最大公约数） 即尼考曼彻斯法，其特色是做一系列减法，从而求得最大公约数。例如 ：两个自然数35和14，用大数减去小数，(35,14)->(21,14)->(7,…
2022/2/17 23:13:33 人评论 次浏览
