做网站用什么,网页游戏奥奇传说,室内设计联盟论坛,网站建设招投标收纳一些天天忘的结论qwq
线性求逆元 invi(p−pi)invpmodiinv_i(p-\dfrac{p}{i})\times inv_{p\bmod i}invi(p−ip)invpmodi
卡特兰数 组合数公式#xff1a;HnC2nn−C2nn−1H_nC_{2n}^n-C_{2n}^{n-1}HnC2nn−C2nn−1 递推式#xff1a;HnHn−1(4n−2)n1H_n\d…收纳一些天天忘的结论qwq
线性求逆元
invi(p−pi)×invpmodiinv_i(p-\dfrac{p}{i})\times inv_{p\bmod i}invi(p−ip)×invpmodi
卡特兰数 组合数公式HnC2nn−C2nn−1H_nC_{2n}^n-C_{2n}^{n-1}HnC2nn−C2nn−1 递推式HnHn−1(4n−2)n1H_n\dfrac{H_{n-1}(4n-2)}{n1}Hnn1Hn−1(4n−2)
欧拉函数 n∑d∣nφ(d)n\sum\limits_{d\mid n} \varphi(d)nd∣n∑φ(d) 欧拉定理gcd(a,m)1,aφ(m)≡1(modm)\gcd(a,m)1,a^{\varphi(m)}\equiv1\pmod mgcd(a,m)1,aφ(m)≡1(modm) 拓展欧拉定理ab≡{abmodφ(m)gcd(a,m)1abgcd(a,m)≠1∧bφ(m)abmodφ(m)φ(m)gcd(a,m)≠1∧b≥φ(m)a^b\equiv\begin{cases}a^{b\bmod \varphi(m)}\quad \gcd(a,m)1\\ a^b\quad \gcd(a,m)\ne 1\land b\varphi(m)\\ a^{b\bmod \varphi(m)\varphi(m)}\quad \gcd(a,m)\ne 1\land b\ge \varphi(m)\end{cases}ab≡⎩⎨⎧abmodφ(m)gcd(a,m)1abgcd(a,m)1∧bφ(m)abmodφ(m)φ(m)gcd(a,m)1∧b≥φ(m)(modm)\pmod m(modm)
数论分块
满足 ⌊ni⌋⌊nx⌋\left\lfloor\dfrac{n}{i}\right\rfloor\left\lfloor\dfrac{n}{x}\right\rfloor⌊in⌋⌊xn⌋ 的最大 xxx 等于 ⌊n⌊ni⌋⌋\left\lfloor\dfrac{n}{\left\lfloor\frac{n}{i}\right\rfloor}\right\rfloor⌊⌊in⌋n⌋
莫比乌斯变换
两个数论函数 f(n),g(n)f(n),g(n)f(n),g(n)若 f(n)∑d∣ng(d)f(n)\sum\limits_{d\mid n} g(d)f(n)d∣n∑g(d)则 g(n)∑d∣nf(d)μ(nd)g(n)\sum\limits_{d\mid n} f(d)\mu(\dfrac{n}{d})g(n)d∣n∑f(d)μ(dn)
阶
使得 an≡1(modm)a^n\equiv1\pmod{m}an≡1(modm) 成立的最小正整数 nnn 叫做 aaa 模 mmm 的阶符号 δm(a)\delta_m(a)δm(a)。
一些性质
∀an≡1(modm),δm(a)∣n⟹δm(a)∣ϕ(m)\forall a^n\equiv 1\pmod{m},\delta_m(a)\mid n\implies\delta_m(a)\mid\phi(m)∀an≡1(modm),δm(a)∣n⟹δm(a)∣ϕ(m)∀i,j∈[1,δm(a)],i≠jai≢aj(modm)\forall_{i,j\in[1,\delta_m(a)],i\ne j}\ a^i\not\equiv a^j\pmod{m}∀i,j∈[1,δm(a)],ij ai≡aj(modm)gcd(a,m)1,δm(ak)δm(a)gcd(k,δm(a))\gcd(a,m)1,\delta_m(a^k)\dfrac{\delta_m(a)}{\gcd(k,\delta_m(a))}gcd(a,m)1,δm(ak)gcd(k,δm(a))δm(a)
原根
若 gcd(a,m)1,δm(a)ϕ(m)\gcd(a,m)1,\delta_m(a)\phi(m)gcd(a,m)1,δm(a)ϕ(m)则 aaa 是 mmm 的原根。
判定定理∀p∣ϕ(m)aϕ(m)p≢1(modm)⟺a\forall_{p\mid \phi(m)} a^{\frac{\phi(m)}{p}}\not\equiv1\pmod{m}\iff a∀p∣ϕ(m)apϕ(m)≡1(modm)⟺a 是 mmm 的原根存在定理只有 2,4,pa,2pa2,4,p^a,2p^a2,4,pa,2pa 才存在原根其中 ppp 为奇素数原根个数若 mmm 有原根则其原根个数为 ϕ(ϕ(m))\phi(\phi(m))ϕ(ϕ(m))mmm 的最小原根 ggg 不超过 m14m^{\frac{1}{4}}m41所有其它原根均为 gk(gcd(k,ϕ(m)1))g^k\ (\gcd(k,\phi(m)1))gk (gcd(k,ϕ(m)1))。
