Blog Remake
Since the structure and context of the old blog is messy and chaotic, the blogger, me, is going to remake the entire blog.
Some articles that I feel pleasant with will be transfered into this new one.
整除与同余
整除与同余
整除定义$\exists q \in \mathbb{Z}$ 使得 $b = a \cdot q$ 则$a \mid b$,其中$a$是$b$的因数,$b$是$a$的倍数
性质
$a\mid b$ 且 $a\mid c$,则$a\mid (b\pm c)$
$a\mid b$,若$c\neq 0$,则$a\mid b\cdot c$
若$ a\mid b $ 且 $b\mid c$,则$a\mid c$
若 $a\mid b$ 且 $a\mid c$,$\forall x,y \in \mathbb{Z}\setminus{0}$,存在$a\mid (b\cdot x+c\cdot y)$
若 $a\mid b$,$\forall m\neq 0$,有$(m\cdot a)\mid (m\cdot b)$
若 $a\mid n$ 且 $b\mid n$ ,$ \exists x,y \in \mathbb{Z}$ ,满足 $a\cdot x+b\cdot y=1$ 时,有 $(a\cdot b)\mid n$
证明
$a\mid b$ 且 $a\mi ...
位运算版快读简析
快读中位运算部分简析
代码1234567891011inline int read() { short int v=1; int s=0; char ch=getchar(); for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') v=-1; for (;ch>='0'&&ch<='9';ch=getchar()) s = (s<<1)+(s<<3)+(ch^'0'); return s*v;}
简析1s = (s<<1)+(s<<3)+(ch^'0');
显然上面那句代码可以加速。
所以这篇博客我将讨论这行位运算的原理。
解析1s = s*10 + ch - '0';
上面这行是不用位运算的版本。
显然,经过 ...
裴蜀定理学习笔记
裴蜀定理
裴蜀定理的内容定理1
若$a,b$是整数,且$\gcd(a,b)=d$,那么对于任意的整数$x,y,ax+by$都一定是$d$的倍数,特别地,一定存在整数$x,y$,使$ax+by=d$成立。
定理2
对于方程$ax+by=1$,只有当整数$a,b$互质时,方程才有整数解。
以上内容摘自百度百科。
裴蜀定理的证明特此说明:以下证明纯属我自己yy,如有错误请联系我指正。
定理1证明我们设$ d=\gcd(a,b) $,则显而易见,$d \mid a$,且$d \mid b$。
根据整除的性质,我们得出$ d \mid ax+by ( x,y \in Z ) $。······(式1.2.1.1)
所以根据(式1.2.1.1)以及整除的意义得出$ ax+by=dk ( k \in Z^+ ) $。
当$k=1$时,则$ax+by=d$。
根据(式1.2.1.1),我们还可以得出$d \mid x$,且$d \mid y$。
至此,定理1证毕。
定理2证明我们可以看出,定理2就是定理1的特殊情况,即$d ...
树旋转学习笔记
平衡树树旋转
代码1234567891011121314inline void left_rotate(int &node){ int r=tree[node].r; tree[node].r=tree[r].l; tree[r].l=node; node=r;}inline void right_rotate(int &node){ int l=tree[node].l; tree[node].l=tree[l].r; tree[l].r=node; node=l;}
分析先上一张树旋转的示意图
图片来自《算法导论》 $\text{P176 13.2}$ 旋转
树旋转的作用树旋转是平衡树上用于维护平衡树平衡的基本操作,有左旋和右旋两种操作
旋转过程分析在进行树旋转时需要维护好二叉搜索树的性质,即
对于每棵子树,都有:
左 < 根 < 右
再看《算法导论》中描述旋转的图片。
以右旋为例,旋转后$\text{x}$代替$\text{y}$作为子树的根节点,由于原来 ...
欧拉筛学习笔记
线性筛质数
代码123456789101112131415161718int prime[MAXN],tot;bool is_prime[MAXN];void choose(int n){ memset(is_prime,1,sizeof(is_prime)); is_prime[1]=0; for(int i=2;i<=n;i++) { if(is_prime[i]) prime[++tot]=i; for(int j=1;j<=tot&&i*prime[j]<=n;j++) { is_prime[i*prime[j]]=0; if(i%prime[j]==0) break; } }}
分析算法分析考虑你在设计一个线性筛质数算法
你想,既然要做到“线性”,那么每个数必须只能被筛一次
所以我们猜想,一个合数只会 ...
快速幂学习笔记
快速幂||取余运算
代码代码(C++):
1234567891011121314151617int quick_pow(int a,int n/*,int p*/){ long long base=a; int ans=1; while(n) { if(n&1) { ans*=base; //ans%=p; } n>>=1; base*=base; //base%=p; } return ans;}
分析本题计算:
$ a^n \mod p $
首先观察$2^5=32$这个式子。
我们知道$5$的二进制为$101$。
我们还知道$32=2^4 \times 2^1$
再来看$2^7=128$,
我们知道$7$的二进制为$111$,
我们还知道$128=2^4 \times 2^2 \times 2^1$ ...
归并排序学习笔记
代码先上伪代码:
12345678910111213141516171819202122232425262728def MERGE(A, p, q, r): n1 = q-p+1 n2 = r-q new L[],r[] for i=1 to n1: L[i] = A[p+i-1] for j=1 to n2: R[j] = A[q+j] L[n1+1] = INF //INF即正无穷 L[n2+1] = INF i=1 j=1 for k=p to r if L[i]<=R[j] A[k] = L[i] i = i + 1 else A[k] = R[j] j = j + 1def MERGE_SORT(A,p,r): if p < r q = floor((p+r)/2) //向下取整 ...
插入排序学习笔记
代码第一个算法就是“插入排序”。伪代码如下:
123456789def INSERTION_SORT(var A[]): var i,j,key; for i=2 to A.length-1: //A.length返回数列以“1”开始时的长度,我们需要-1 key = A[i]; j = i-1; while j>-1 and A[j]>key: //算法导论中原是“while i>0 and A[i]>key” A[j+1]=A[j]; j-=1; A[j+1]=key;
转换成C++代码后是这样:
12345678910111213141516171819202122#include<iostream>using namespace std;int main() { int a[10]={0}; int i,j,key; int n; cin >> ...