模运算规则
Created|Updated
|Word Count:177|Reading Time:1mins|Post Views:
模运算与基本四则运算有些相似，但是除法例外。其规则如下：
(a + b) % p = (a % p + b % p) % p
(a - b) % p = (a % p - b % p) % p
(a * b) % p = (a % p * b % p) % p
(a^b) % p = ((a % p)^b) % p
推论：
若a≡b (% p)，则对于任意的c，都有(a + c) ≡ (b + c) (%p)；
若a≡b (% p)，则对于任意的c，都有(a * c) ≡ (b * c) (%p)；
若a≡b (% p)，c≡d (% p)，则 (a + c) ≡ (b + d) (%p)，(a - c) ≡ (b - d) (%p)，
(a * c) ≡ (b * d) (%p)，(a / c) ≡ (b / d) (%p)；
费马定理：若p是素数，a是正整数且不能被p整除，则：a^(p-1) mod p = 1 mod p
推论：若p是素数，a是正整数且不能被p整除，则：a^p mod p = a mod p
Related Articles
2020-07-24
算法与数据结构学习笔记：链表
核心知识点 null异常处理 dummy node 哑巴节点 双指针/快慢指针 插入一个节点到排序链表 从一个链表中移除一个节点 翻转链表 合并两个链表 找到链表的中间节点 例题：83. 删除排序链表中的重复元素 给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。 示例 1: 输入: 1->1->2输出: 1->2示例 2: 输入: 1->1->2->3->3输出: 1->2->3 直接法：链表是有序的，所以直接更改当前结点的 next 指针，跳过下一个结点并直接指向下一个结点之后的结点即可。 123456789101112131415161718192021222324252627282930/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */cl...
2020-08-06
算法与数据结构学习笔记：二叉树
知识点二叉树遍历前序遍历：先访问根节点，再前序遍历左子树，再前序遍历右子树 中序遍历：先中序遍历左子树，再访问根节点，再中序遍历右子树 后序遍历：先后序遍历左子树，再后序遍历右子树，再访问根节点 注意点 以根访问顺序决定是什么遍历 左子树都是优先右子树 前序遍历例题：https://leetcode-cn.com/problems/binary-tree-preorder-traversal/ 递归123456789101112131415161718192021222324/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: vector<int> ans; vector<int&g...
2020-09-11
算法与数据结构学习笔记：栈和队列
简介栈的特点是后入先出，根据这个特点可以临时保存一些数据，之后用到依次再弹出来，常用于 DFS 深度搜索 队列一般常用于 BFS 广度搜索，类似一层一层的搜索 栈155. 最小栈 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。 push(x) —— 将元素 x 推入栈中。pop() —— 删除栈顶的元素。top() —— 获取栈顶元素。getMin() —— 检索栈中的最小元素。 辅助栈12345678910111213141516171819202122232425262728293031323334353637383940class MinStack {public: /** initialize your data structure here. */ stack<int> minStack; stack<int> dataStack; MinStack() { minStack.push(INT_MAX); } void push(in...
2020-09-07
算法与数据结构学习笔记：二进制
常见二进制操作C++位运算符下表显示了 C++ 支持的位运算符。 假设如果 A = 60，且 B = 13，现在以二进制格式表示，它们如下所示： A = 0011 1100 B = 0000 1101 则： 运算符 描述 实例 & 如果同时存在于两个操作数中，二进制 AND 运算符复制一位到结果中。 (A & B) 将得到 12，即为 0000 1100 | 如果存在于任一操作数中，二进制 OR 运算符复制一位到结果中。 (A | B) 将得到 61，即为 0011 1101 ^ 如果存在于其中一个操作数中但不同时存在于两个操作数中，二进制异或运算符复制一位到结果中。 (A ^ B) 将得到 49，即为 0011 0001 ~ 二进制补码运算符是一元运算符，具有”翻转”位效果，即0变成1，1变成0。 (~A ) 将得到 -61，即为 1100 0011，一个有符号二进制数的补码形式。 << 二进制左移运算符。左操作数的值向左移动右操作数指定的位数。 A << 2 将得到 240，即为 1111 0000 &g...
2020-09-11
算法与数据结构学习笔记：动态规划
背包问题0 1 背包每件物品最多只用一次 完全背包每件物品有无限个 多重背包分组背包线性 DP最经典单串300. 最长上升子序列 给定一个无序的整数数组，找到其中最长上升子序列的长度。 示例: 输入: [10,9,2,5,3,7,101,18]输出: 4解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。 12345678910111213141516171819class Solution {public: int lengthOfLIS(vector<int>& nums) { int maxLength=0; vector<int> dp(nums.size(),1); for(int i=0;i<nums.size();i++) { for(int j=0;j<i;j++) { if(nums[i]>nums[j]&&dp[i]<(dp[j]+1))...
2020-09-11
算法与数据结构学习笔记：二分法
二分搜索模板给一个有序数组和目标值，找第一次/最后一次/任何一次出现的索引，如果没有出现返回-1 模板四点要素 1、初始化：start=0、end=len-1 2、循环退出条件：start + 1 < end 3、比较中点和目标值：A[mid] ==、 <、> target 4、判断最后两个元素是否符合：A[start]、A[end] ? target 注意：为了防止overflow，超过int范围，左中位数（a+b)=a+(b-a)/2,右中位数（a+b)=a+(b-a+1)/2如果有mid*mid,mid用int注意溢出 时间复杂度 O(logn)，使用场景一般是有序数组的查找 典型示例 704. 二分查找 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。 1234567891011121314151617181920212223242526class Solution {public: int search(vector&...