搜索结果
查询Tags标签： bmod，共有 16条记录-
质数判定的常数优化
注意：下面可能有部分数学符号使用不规范，看懂就行。 如何迅速判断 \(n\) 是否为质数？ 方法一 枚举 \(i\) 满足 \(1 < i < n\)，则 \(n\) 不是质数，当且仅当全部的 \(i \nmid n\)。 时间复杂度 \(O(n)\)。 bool isp(int n) //isp = is_prime {if (n <= 1) ret…
2022/8/26 6:23:33 人评论 次浏览 -
万能欧几里得算法学习笔记
万能欧几里得算法 基本描述 对于一条直线 \(\dfrac {px+r}{q}\)，满足 \(p>0,q>0,r\in[0,q-1]\)，求解有关 \(\lfloor\dfrac {px+r}{q}\rfloor,x\) 的一些函数。 考虑在坐标系上考虑这条直线，从 \((0,0)\) 开始走。 定义当直线穿过一条形如 \(y=h(h\in\Z)\) 的横线…
2022/8/6 1:23:52 人评论 次浏览 -
P1516 青蛙的约会
题目传送门 思路 因为两个青蛙同时跳到同一个点上才算碰面，设 $ t $ 为跳的次数， $ p $ 为两个青蛙跳的圈数之差，有如下式子： \[(x+m \times t ) - ( y+n \times t ) = p \times L \]整理得： \[(n-m) \times t + L \times p = x - y \]首先，要判断 $ \gcd ( n-m ,…
2022/7/31 23:39:32 人评论 次浏览 -
乘法逆元学习笔记
乘法逆元和求法 基本的数论知识，有必要补一发。 开始之前模运算：取余运算，比如 \(a \bmod b\) 就是 \(a\) 除以 \(b\) 得到的余数。性质：在加、减、乘、乘方的运算过程中，进行取余运算，不会对结果产生影响。优先级：取余运算的优先级和乘法、除法的优先级相同，高于…
2022/4/30 23:14:13 人评论 次浏览 -
中国剩余定理
简介 中国剩余定理 (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 人评论 次浏览 -
蓝桥杯2022研究生C/C++组
A、裁纸刀 好难。不会。 B、灭鼠先锋 博弈论。 首先、对于棋盘的任一种情况都是必赢或者必输。 基本思路： 如果我存在放置一个棋子，或在同一行的连续两个空位上各放置一个棋子可以赢，我就必赢，否则我必输。然后不断递归即可。 答案：VVVL C、质因数个数 枚举\(~2\sim\…
2022/4/10 17:13:05 人评论 次浏览 -
欧几里得算法
欧几里得算法 描述 \[\gcd(a, b) = \gcd(b, a \bmod b) \]证明 求证： \[\gcd(a, b) = \gcd(b, a \bmod b) \]假设 \(a > b\) 且 \(b \nmid a\)，可描述： \[a = bk + c \]其中 \(k\) 为商，\(c\) 为余数。 假设 \(\gcd(a, b) = u\) \(a = xu, b = yu\)，显然 \(x\) 与…
2022/2/3 20:13:08 人评论 次浏览 -
清北灵堂送走记 Day2
清北灵堂送走记 \(Day2\) 前言 数论专题，鬼知道我这三天经历了什么 同余若 \(a,b\) 为两个整数，且他们的差 \(a-b\) 能被某个自然数 \(m\) 所整除，则称 \(a\) 和 \(b\) 关于 \(m\) 同余，记作 \(a \equiv b \pmod m\)。它意味着 \(a-b = m \times k\)。 一些性质：…
2022/1/26 23:09:45 人评论 次浏览 -
CF450B Jzzhu and Sequences 题解
Content 有一个长度为 \(n\) 的数列 \(\{a_1,a_2,\dots,a_n\}\)，满足如下的递推公式：\(i=1\) 时，\(a_1=x\)。 \(i=2\) 时，\(a_2=y\)。 \(i\geqslant 3\) 时，\(a_i=a_{i-1}+a_{i+1}\)。求 \(a_n\bmod 10^9+7\) 的值。 数据范围：\(1\leqslant n\leqslant 2\times 10^9…
2021/12/15 23:44:04 人评论 次浏览 -
CF450B Jzzhu and Sequences 题解
Content 有一个长度为 \(n\) 的数列 \(\{a_1,a_2,\dots,a_n\}\)，满足如下的递推公式：\(i=1\) 时，\(a_1=x\)。 \(i=2\) 时，\(a_2=y\)。 \(i\geqslant 3\) 时，\(a_i=a_{i-1}+a_{i+1}\)。求 \(a_n\bmod 10^9+7\) 的值。 数据范围：\(1\leqslant n\leqslant 2\times 10^9…
2021/12/15 23:44:04 人评论 次浏览 -
CSP-S 2021 初赛解析
一、单项选择解析 1.选A，ls列出目录，cd是定位目录，cp是复制问卷,all只有作为命令的参数使用 2.选B，00101010+ 00010110010000003.选A，递归函数的参数和局部变量存储在系统栈，如果层数过多，栈就会溢出。 解析 4.选C，排序稳不稳定看相等值得元素排序后得相对位置有没…
2021/10/18 23:10:46 人评论 次浏览 -
CSP-S 2021 初赛解析
一、单项选择解析 1.选A，ls列出目录，cd是定位目录，cp是复制问卷,all只有作为命令的参数使用 2.选B，00101010+ 00010110010000003.选A，递归函数的参数和局部变量存储在系统栈，如果层数过多，栈就会溢出。 解析 4.选C，排序稳不稳定看相等值得元素排序后得相对位置有没…
2021/10/18 23:10:46 人评论 次浏览 -
P1965 [NOIP2013 提高组] 转圈游戏
Problem 给定\(n,m,k,x\)，\(x\)每次会变成\((x + m) \bmod n\)，称为1次变换，求经过\(10^k\)次变换后\(x\)的值。 \(n \le 10^6,m < n,k,x \le 10^9\)。 Solution 看见\(n\)数据范围显然可以想到整循环节，但是我们不会推，咋办，发现求循环节至多\(\mathcal{O}(n)\)…
2021/9/11 6:06:23 人评论 次浏览 -
P1965 [NOIP2013 提高组] 转圈游戏
Problem 给定\(n,m,k,x\)，\(x\)每次会变成\((x + m) \bmod n\)，称为1次变换，求经过\(10^k\)次变换后\(x\)的值。 \(n \le 10^6,m < n,k,x \le 10^9\)。 Solution 看见\(n\)数据范围显然可以想到整循环节，但是我们不会推，咋办，发现求循环节至多\(\mathcal{O}(n)\)…
2021/9/11 6:06:23 人评论 次浏览 -
同余最短路
当出现类似给定 \(a_1,a_2,\dots,a_n\),求满足 \(\sum_{i=1}^na_ix_i=b\) 有整数解的 \(b\) 的个数的问题时，一般采用同余最短路的方法。 上类题型的转移方程大多都是 \(f_{i+x}=f_i+x\)，而它与单源最短路中的 \(dis_v=dis_i+edge_{u,v}\)类似，因此我们可以由此来建边。…
2021/6/13 18:51:04 人评论 次浏览
