6/1奥数 1.逆元的应用: 中国剩余定理  说明：  例一:  答案:  例二:  方法:  答案:  把大的模的同余方程变为小的模的同余方程  例一:  方法:  方法小结:  拓展中国剩余定理

1.一次同余方程组 简介:与一元一次不等式组相似，就不给出了 例1:  解法:  例二:  解法:  例三:  解法:通过定理1可知无解。 定理1:  代码: int extended_gcd(int a, int b, int &x, int &y) { if (b == 0) { x = 1; y = 0; return a; } int x1, y1; int gcd = extended_gcd(b, a % b, x1, y1); x = y1; y = x1 - (a / b) * y1; return gcd; } // 解同余方程 a*x ≡ b (mod m)...

5/11日奥数 上半节 1.形式分数法:  2.例子:  解法:  3.扩展欧几里得算法(EXEA) 1.背景  2.步骤如下:   3.扩展欧几里得算法代码实现: #include <iostream> #include <tuple> using namespace std; tuple<int, int, int> gcdd(int a, int b) { if (b == 0) { return {a, 1, 0}; // gcd = a, x = 1, y = 0 } int gcd, x1, y1; tie(gcd, x1, y1) = gcdd...

树形dp(自下而上)↓T1分析维度:f[i]表示以i为根的子树的所有点到i的距离之和。初始化:f[1]=0转移:但是如果我们枚举每一个i，那就TLE了，此时我们就要使用换根dp，用原来一个点的结果在O(n)的时间内算出其他点的结果(自上而下)，如下图:完整代码: #include<bits/stdc++.h> #define endl '\n' using namespace std; const int maxn=1e5+1; vector<int> z[maxn]; int f[maxn],ans,n; int size[maxn]; void dfs(int no...

五一普转提笔记Day-3免责声明:本人并非原创者，如有不对请指出，勿喷。上午1.lower_bound 和 upper_boundlower_bound(首元素地址，尾元素地址的下一个地址，目标数)找到第一个不小于k的元素的地址upper_bound(首元素地址，尾元素地址的下一个地址，目标数)找到第一个大于k的元素的地址代码： #include<bits/stdc++.h> #define endl '\n' using namespace std; signed main(){ int n=10; int a[15]; set<int> se; for(int i=...

清北学堂五一集训Day-1上午1.在比赛时尽量使用'\n'，不要用endl2.队列(FIFO)stl队列： #include<queue> //#include<bits/stdc++.h> using namespace std; queue<int> q; //queue<队列里面的元素类型> 变量名; int main() { q.push(233); q.push(2233);//向队列里面加入一个元素 q.pop();//从队列中删除一个元素 删除是队列头的元素 233 void类型没有返回值 int x = q.front();//获...

五一普转提Day-2上午1.线段树（分治）主要用来解决区间存储的问题每一个节点都对应一个区间1.有层，最多个区间2.有个节点3.计算区间和，自下而上计算，上面一个等于下面的和4.区间求和把几个区间找出来再加起来就可以了5.空间要开为倍6.建树的代码 #include<bits/stdc++.h> #define int long long #define endl '\n' using namespace std; const int maxn=1000010; int n,m,a[maxn]; struct node{ int sum;//区间和 int size;//区间长度 ...