hetao22179092 (唐衍硕)
UID: 19446, 注册于 2023-7-29 15:56:57, 最后登录于 2024-8-10 18:46:02, 目前离线.
解决了 2 道题目，RP: 14 (No. 1)
-
个人简介
😄 大家好啊，我只是一名普普通通的C++小创客* [ 文章列表 - Michael_Corleone 的博客 - 洛谷博客 (luogu.com.cn)]，喜欢编程蛤😄
亿点芝士 【芝士】的力量是无穷的
数论
1. 位运算(&,|,^,>>,<<,~)
①异或运算的逆运算是它本身，也就是说两次异或同一个数最后结果不变，即
aa \bigoplus⨁ bb \bigoplus⨁ bb=aa。
②取反：二进制补码按位取反，有符号位也会取反。右移就是除以2，左移就是乘2.
③位运算的优先级低于算术运算符（除了取反），而按位与、按位或及异或低于比较运算符
④位运算的应用,位运算一般有三种作用：
(1) 高效地进行某些运算，代替其它低效的方式。
(2) 表示集合。（常用于状压 DP)
(3) 题目本来就要求进行位运算。
判断一个数是不是2的非负整数次幂：
n & (n - 1)== 0;对2的非负整数次幂取模：
x & (mod - 1);获取 a 的第 b 位，最低位编号为 0
int getBit(int a, int b) { return (a >> b) & 1; }将 a 的第 b 位设置为 0 ，最低位编号为 0
int unsetBit(int a, int b) { return a & ~(1 << b); }2. 快速幂
加速快速幂：根据费马小定理，如果p是一个质数，而整数a不是p的倍数，则有
a^{（p-1）}≡1（mod p）a（p−1）≡1**（modp**）。
3. 扩展欧几里得定理
- gcd(a,b)=gcd(b,agcd(a,b)=gcd**(b,**a%b)b)
- 用于解ax+by=cax**+by**=c不定方程的解(a,x,b,y都是整数a,x,b,y都是整数)，根据裴蜀定理，ax+by=cax**+by**=c有解的充分必要条件是cc%gcd(a,b)0gcd(a,b)**0,给出证明，设gcd(a,b)==dgcd**(a,b)**==d,则a=nd,b=mda=nd**,b=md**。则ndx+mdy=cndx+mdy=c，化简得d(nx+my)=cd(nx**+my**)=c，则cc一定是dd**的倍数，证毕。
- 实际是先ax+py=gcd(a,b)a∗x+p∗y=gcd(a,b)这个方程后，反推出原方程的解，给解出来的xc/gcd(a,b)x∗c/gcd(a,b)就是ax+by=cax**+by**=c的一个解，那么我们解这个方程首先根据裴蜀定理进行化简，令a=b,b=aa=b,b=a%bb，则该式子是bx+abx**+a%by=gcd(b,aby=gcd(b,a%b)b),由于gcd(b,agcd**(b,a%b)b)=gcd(a,b)=gcd**(a,b),得 bx+abx+a%by=gcd(a,b)by=gcd(a,b)**, 即ay-b(x-a/by)=gcd(a,b)ay−b**(x−a/b∗y)=gcd**(a,b),递归求解到最后，b==0的时候，得到一组解，x=1,y=0x=1,y=0.也就是a1+b0=gcd(a,0)a∗1+b∗0=gcd(a,0),gcd(a,0)gcd(a,0)当然就是aa了.
int exgcd(int a,int b,int &x,int &y) { if(b==0) { x=1,y=0; return a; } int d=exgcd(b,a%b,x,y); int t=x; x=y; y=t-a/b*y; return d; }- 此时得到的xx只是ax+by=gcd(a,b)ax**+by**=gcd(a,b)的一组特解，ax+kab-kab+by=cax**+kab−kab+by**=c,则a(x+kb)+b(y-ka)=ca(x+kb)+b(y−ka**)=c.我们将要求出来的 x,yx**,y 仅仅保证满足 ax + by = 1ax**+by**=1而 xx 不一定是最小正整数解。有可能太大，也有可能是负数
- 根据特解，x=x*c/gcd(a,b)x=x∗c/gcd(a,b)就得到原方程的一组解。所以如果xx太小，我们就加bb刚好大于等于00，反之减bb。
- 最小非负整数解：(x**(x%(b/d)+b/d)(b/d)**+b/d)%(b/d)(b/d),需注意若a<0a**<0**，需改变符号。
- 显然最小时 d_x=\frac{b}{\gcd(a,b)}dx=gcd(a,b)b， d_y=\frac{a}{\gcd(a,b)}dy=gcd(a,b)a，在d=\frac{1}{\gcd(a,b)}d=gcd(a,b)1时取到
那么通解形式就出来了，
x=x_1+sd_x xx=x1+sdxx y=y_1-sd_yy=y1−sdy 其中，ss 是任意整数
而且，随着 xx 增大 yy减小 （废话，它们的和一定）
而且，ss 越大，xx 越大，yy越小，反之亦然（重点）
4. 质因数分解
for (int i = 2; i * i <= n; i++) { if (n % i == 0) { int cnt = 0; while (n % i == 0) { n /= i; cnt++; } v.push_back((node){i, cnt}); } } if (n != 1) { v.push_back((node){n, 1}); }- 要使得s_i^k \mid m_1^{m_2}sik∣m1m2,则si分解的质因数必须包含m1的所有质因子。
5.线性复杂度解决1~n mod p的逆元(pp为质数)
过程：
- 令p=ki+rp=ki+r,kk为p/ip/i的商，rr为余数。则k=⌊p/i⌋k=**⌊p/i⌋（向下取整）, r=p \ mod\ ir=p mod** i.(i<p,k<p,r<ii<p,k<p,r<i)
- 两边同时乘以i^{-1}r^{-1}i−1∗r−1,得到kr^{-1}+i^{-1}\equiv\ 0 (mod\ p)k∗r−1+i−1≡** 0(mod p)**
- 移项得i^{-1}\equiv -k*r^{-1}(mod\ p)i−1≡−k∗r−1**(mod p)**
- 带入刚才得kk和rr的表达式,得到i^{-1}\equiv -⌊p/i⌋*(p \ mod\ i)^{-1}(mod\ p)i−1≡−⌊p/i⌋∗(p mod i)−1**(mod p)**
- 由于p \ mod\ i<ip mod i<i,所以在求出i^{-1}i−1之前已经求出(p \ mod\ i)^{-1}(p mod** i)−1**
- 用数组inv[i]记录i^{-1}i−1,则inv[i]=-p/i*inv[p \ mod\ i]\ mod \ p−p**/i∗inv**[p mod i]** mod **p
- 同时要注意，为了保证i^{-1}>0i−1>0，上式需要两边加上p。
- 则inv[i]={p-p/i*inv[p \ mod\ i]\ mod \ p}p−p/i∗inv**[p mod i]** mod p
- 然后可以轻松的由inv[1]=1inv**[1]**=1,在O(1)的时间推出其余答案。
- 正常可以利用exgcd和快速幂结合费马小定理在log时间解决
6.中国剩余定理
常用来解一元线性同余方程组
一般从这个问题引入，某物品三三数之余二，五五数之余三，七七数之余二。问物几何？
写成方程组的形式就是求解
\left{ \begin{matrix} x\equiv\ 2\ mod\ 3 \ x\equiv\ 3\ mod\ 5 \ x\equiv\ 2\ mod\ 7 \end{matrix} \right.⎩⎨⎧x≡ 2 mod 3x≡ 3 mod 5x≡ 2 mod 7
首先，若x_0x0为原方程的一个解，那么x_0+357*k，k\in 整数x0+3∗5∗7∗k，k∈整数，也是一个解
解上述方程组其实首先需要解以下3个方程，这里有点线性代数的意思。
\left{ \begin{matrix} x\equiv\ 1\ mod\ 3 \ x\equiv\ 0\ mod\ 5 \ x\equiv\ 0\ mod\ 7 \end{matrix} \right.⎩⎨⎧x≡ 1 mod 3x≡ 0 mod 5x≡ 0 mod 7
\left{ \begin{matrix} x\equiv\ 0\ mod\ 3 \ x\equiv\ 1\ mod\ 5 \ x\equiv\ 0\ mod\ 7 \end{matrix} \right.⎩⎨⎧x≡ 0 mod 3x≡ 1 mod 5x≡ 0 mod 7
\left{ \begin{matrix} x\equiv\ 0\ mod\ 3 \ x\equiv\ 0\ mod\ 5 \ x\equiv\ 1\ mod\ 7 \end{matrix} \right.⎩⎨⎧x≡ 0 mod 3x≡ 0 mod 5x≡ 1 mod 7
记上述三组的解记为
\begin{bmatrix} 1\ 0\ 0\ \end{bmatrix}⎣⎡100⎦⎤
\begin{bmatrix} 0\ 1\ 0\ \end{bmatrix}⎣⎡010⎦⎤
\begin{bmatrix} 0\ 0\ 1\ \end{bmatrix}⎣⎡001⎦⎤
则原方程的解为 22∗\begin{bmatrix} 1\ 0\ 0\ \end{bmatrix}⎣⎡100⎦⎤*+33∗\begin{bmatrix} 0\ 1\ 0\ \end{bmatrix}⎣⎡010⎦⎤*+22∗\begin{bmatrix} 0\ 0\ 1\ \end{bmatrix}⎣⎡001⎦⎤*
问题的关键显然是求上述三组解。 上述三组解是这样求的，先来看第一个。
\left{ \begin{matrix} x\equiv\ 1\ mod\ 3 \ x\equiv\ 0\ mod\ 5 \ x\equiv\ 0\ mod\ 7 \end{matrix} \right.⎩⎨⎧x≡ 1 mod 3x≡ 0 mod 5x≡ 0 mod 7
x一定是35的倍数x一定是35的倍数，所以设x=35*yx=35∗y,那么35y\ \equiv\ 1\ mod\ 335y** ≡ 1 mod 3,这里容易求出yy是22**,实际也能看出就是逆元。
求出22以后，x=35*2=70x=35∗2=70，那么第一个方程组的一个特解就出来了。
同理求出其余的两个方程组的特解分别是x=21,x=15x=21,x=15。
则原方程的解为270+321+2*15\ \equiv\ 23\ mod\ 1052∗70+3∗21+2∗15 ≡ 23 mod 105 ，所以这里就求出了23.
因此从这里也能看出线性同余方程组的求解方式，方法就是。
\left{ \begin{matrix} x\equiv\ b_1\ mod\ a_1 \ x\equiv\ b_2\ mod\ a_2 \ …… \ x\equiv\ b_k\ mod\ a_k \ \end{matrix} \right.⎩⎨⎧x≡ b1 mod a1x≡ b2 mod a2……x≡** bk mod ak**
首先还是按照刚才的方式分出多个方程组来，求出每一个的，最后求和。
- 首先求出N=a_1a_2……a_kN=a1∗a2∗*……∗ak**
- 对于每一组方程我们按照上面的例题思路来求解，设m=N/a_im=N/ai,那么紧接着我们需要求出mx\ \equiv\ 1\ mod\ a_imx** ≡ 1 mod ai,求出这个x以后x**以后。
- 那么最终这个方程组的解就是mxb_im∗x∗bi，回想刚才不就是35是m，x求逆元是2，b_i是235是m，x求逆元是2，bi是2，所以是352235∗2∗2,对应上面的2*702∗70.
- 然后循环求和，并且求和的时候对NN取余得到答案。
7.扩展中国剩余定理
求解同余方程组
\left{\begin{aligned}x\equiv\ a_1(\mod m_1) \quad\ x\equiv\ a_2(\mod m_2) \quad\ x\equiv\ a_3(\mod m_3) \quad\ ...\quad\x\equiv\ a_k(\mod m_k) \quad\end{aligned}\right.⎩⎨⎧x≡ a1(modm1**)x≡** a2(modm2**)x≡** a3(modm3**)...x≡ ak(modmk**)其中m_1,m_2,m_3...m_km1,m2,m3...mk
为不一定两两互质的整数， 求xx的最小非负整数解.
类似于求多个数字gcdgcd 的方法，先求出前两个的解，然后不停的合并，前两个方程组可以利用扩欧求出最小解，然后循环下去即可。
ll tmp1 = b[1], tmp2 = a[1], ans; for (int i = 2; i <= n; i++) { ll A, B, C, X, Y; C = b[i] - tmp1; A = tmp2, B = a[i]; if (C < 0) { swap(b[i], tmp1); swap(A, B); } ll g = gcd(A, B); C = b[i] - tmp1; exgcd(A, B, X, Y); X *= C / g, Y *= C / g; Y %= A / g; if (Y > 0) { Y -= A / g; } ans = (b[i] - B * Y) % lcm(a[i], tmp2); tmp1 = (b[i] - B * Y) % lcm(a[i], tmp2); tmp2 = lcm(a[i], tmp2); }8.Lucas定理
定理用于求解大组合数取模的问题，其中模数必须为素数。正常的组合数运算可以通过递推公式求解（详见 排列组合），但当问题规模很大，而模数是一个不大的质数的时候，就不能简单地通过递推求解来得到答案，需要用到 LucasLucas 定理。
公式：C(n,m)\ mod\ p=C(n/p,m/p)*C(n%p,m%p)\ mod\ pC(n,m)** mod p=C(n/p,m/p)∗C**(n%p,m%p)** mod **p
递归操作下去，当 m==0m0,返回11.也就是C(n,0)1C(n,0)**==**1
Lucas(n,m)\ mod\ p=Lucas(n/p,m/p)C(n%p,m%p)\ mod\ pLucas*(n,m)** mod p=Lucas**(n/p,m/p)∗C**(n%p,m%p)** mod **p
ll Lucas(ll n, ll m, ll p) { if(m == 0)return 1; return C(n % p, m % p, p) * Lucas(n / p, m / p, p) % p; }求解C(n%p,m%p)\ mod\ pC(n%p,m%p)** mod **p的时候
当n,mn,m不大的时候，可以预处理出所有的阶乘答案存到数组。数字大的时候可以单独去算。
C(n,m)=n!/(n-m)!m!C(n,m)**=n!/(n−**m*)!∗m**!也就是(n*(n-1)*……*(n-m+1))/m!\ mod\ p**(n∗**(n−1)∗……∗(n−m+1))/m! mod p 分子分母都可以直接计算，牵扯到除法因此需要求m!*x\equiv\ 1\ mod\ pm!∗x≡ 1 mod p求出这个xx,也就是逆元，由于pp是质数，因此用费马小定理求解即可。
ll quick_pow(ll a, ll b, ll mod) { ll ans = 1; while (b) { if (b & 1) { ans *= a; ans %= mod; } a *= a; a %= mod; b >>= 1; } return ans; } ll inv(ll a, ll p) //求a mod p下的逆元。 { return quick_pow(a, p - 2, p); } ll C(ll n, ll m, ll p) { if (m > n) return 0; ll up = 1, down = 1; for (int i = n - m + 1; i <= n; i++) up = up * i % p; for (int i = 1; i <= m; i++) down = down * i % p; return up * inv(down, p) % p; } 你学费了吗 不过我没学费 ```cpp #include<bits/stdc++.h> using namespace std; namespace IO{ template <typename T> inline void read(T &x){ x = 0; register int t = 1; register char ch = getchar(); while(ch < '0' || ch > '9'){ if(ch == '-') t = -1; ch = getchar(); } while(ch >= '0' && ch <= '9'){ x = (x << 3) + (x << 1) + ch - '0'; ch = getchar(); } x *= t; } template <typename T> inline void write(T x){ if(x < 0){ putchar('-'); x = -x; } if(x > 9) write(x / 10); putchar(x % 10 + '0'); } }数学区
整活区
OI重点
T M D S B 贪心 枚举 DP 搜索 二进制~请不要对这几个字母有其他的理解。~
励志区
- Always continue; Never break. ——小粉兔
- 在纷繁杂乱的世界里，独自寻找属于自己的光荣与梦想。——StudyingFather
- 有志不在年高，无志空长百岁。——离散小波变换°
- “我要再和生活死磕几年。要么我就毁灭，要么我就注定铸就辉煌。如果有一天，你发现我在平庸面前低了头，请向我开炮。”——皎月半洒花
- 如果命运对你缄默，你就活给他看。——command_block
- “人生就像动态规划，你的一个又一个阶段是由上天安排的，而你，决定的是在这一阶段可以由上一阶段的哪些状态转移而来。越勤奋，越幸运，并不代表这一次你决策的方向有多么优秀，却代表着现在的这一个状态能够续写多少可能的结果。”——天上一颗蛋
- 失败不是什么丢人的事情，从失败中全无收获才是。
- 一个人的成功与否不在于他在得意时能走的多快，而在于他在失败时能多快停止退步。——KMP
- 上坡路都是不好走的，好走的只有下坡路。
写在最后
回洛谷看看，是怀着一丝敬佩的。
竞赛加分取消后，身边不知多少人多少学校将 OI 扔进了垃圾堆。
我这个人吧是那种不爱看重成绩去什么什么很好的大学才有出路。
但即便是我，也不能说当初选择信息竞赛没有考虑过功利。
谁不曾梦想过金牌保送清北呢？
肉麻的话我说不出，也不想说。
但你们，仍然坚持着的你们，实实在在地仍挺直着不屈的脊背。
你们是凭着一片热忱还坚守着这片土地啊！
也许有一天，你发现，付出了许多的你，和也许没那么努力的其他人相比，都能踏入挺厉害的大学，都有着美好的前程。
你也许会浮想联翩：要是我当初没踏足 OI ，我会不会在一个更好的地方？
这时，请不要后悔。
绕远的路，总有风景。
——P3369题解 by天上一颗蛋
-
通过的题目
-
最近活动
This person is lazy and didn't join any contests or homework. -
最近编写的题解
This person is lazy and didn't write any solutions.
题目标签
- 客观题
- 1