0%

线性筛是数论中主要的算法,在求素数、配合算数基本定理求积性函数中有重要作用。

本文研究线性筛和和线性筛的具体应用。

Read more »

圆方树是解决一类仙人掌问题的优秀方法。

广义圆方树是解决无向图路径问题的优秀方法,思路简单暴力且优雅。

这篇文章并不讨论解决仙人掌的圆方树,而是介绍广义圆方树和题目。

Read more »

差分约束

建边套路

Read more »

过分简单的一道数论题,然而想了很长时间才做出来,记录一下。

问题为求:

Read more »

Native

中国剩余定理用于求解线性同余方程组。

描述为:

设自然数 $m_1,m_2,m_3,…,m_r$ 两两互质,并记 $M=\prod^r_{i=1}m_i$,则

Read more »

Native

若 $a × x \equiv 1(mod \ b)$,$a,b$ 互质,则称 $x$ 为 $a$ 的逆元,记为 $a^{-1}$。

逆元用于计算 $t/a \ mod \ b$ 时,转化为 $t×a^{-1} \ mod \ b$。

求逆元

拓展欧几里德

有一个在线性同余方程部分没有记录的性质:

Read more »

GCD

求Gcd

两种常用方法,均基于辗转相除,第二种方法在某些问题的处理上可能出锅。

1
2
3
4
5
6
7
inline int gcd(int x,int y){
return y==0?x:gcd(y,x%y);
}
inline int _gcd(int x,int y){
while(y^=x^=y^=x%=y);
return x;
}
求LCM

$gcd(a,b)lcm(a,b)=ab$

Read more »