Aurouki

二分+ST表求gcd题目链接：https://codeforces.com/contest/1548/problem/B题意由不同正整数组成的数组a,求最大子数组的长度，使得存在正整数且 mod m = mod m = = mod m. 题解     由gcd的性质可知，,所以要判断一个子区间是否满足模m相等，只需要建立一个差分数组，最终使得区间的gcd值大于1即可；考虑到本题是静态的数据，且gcd值满足结合律，所以我们可以对GCD值建立一个ST表，就能够高效地查询区间GCD的值.     接下来，我们枚举左端点l,可以通过二分查找的方式到符合条件的最右端，再对每一个值进行维护最大值的操作. code: #include #define int long long #define endl '\n' #define INF 1e15 using namespace std; typedef pairpii; int a[200010], diff[200010][35]; signed main(){ std::ios::sync_with_stdio(fals ...

A.Maximize(枚举)题意每次给定一个正整数x,寻找一个y()，满足gcd(x,y)+y的值最大；若有多个y满足条件，则输出一个即可. 数据范围 思路由于t和x的值域都极小，只需要对y进行暴力枚举并维护最大值即可. Code:12345678910111213141516171819202122#include<bits/stdc++.h>#define int long long#define endl '\n' using namespace std;int gcd(int a,int b){ return b == 0 ? a : gcd(b, a % b);}signed main(){ std::ios::sync_with_stdio(false);cin.tie(0); int t;cin >> t; while(t--){ int x;cin >> x; int ans = 0, idx; for (int i = x-1; i >= 1;i--){ ...

无边权BFS有边权全源最短路Floyd 算法（时间复杂度：O（））1234567void floyd(){ for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) if (dist[i][k] != INF && dist[k][j] != INF && dist[i][j] > dist[i][k] + dist[k][j]) dist[i][j] = dist[i][k] + dist[k][j];} 单源最短路径Dijkstra算法朴素（时间复杂度：O（））1234567891011121314auto Dijkstra = [&]() -> void{ dist[s] = 0; int cur = s; while (!vis[cur]){ vis[cur] = 1; for ...

123456789101112131415161718int trie[30][100010]; //trie[i][N]表示以i为结点，N为子节点值的编号（初始为零）void add(string x){ int u = 0,num = s.length(); for(int j = 0;j < num;j++){ int p = s[j] - 'a'; if(!trie[u][p])trie[u][p] = ++ idx; u = trie[u][p]; }}int query(string s){ int res = 0, u = 0, num = s.length(); for(int j = 0; j < num; j++){ int p = s[j] - 'a'; u = trie[u][p]; res += cnt[u]; } ...

并查集12345678910for(int i = 1;i <= n; i++) fa[i] = i;int find(int x) { //路径压缩 return (fa[x] == x ? x : fa[x] = find(fa[x]));}void merge(int x, int y) { int px = find(x), py = get(y); if(px == py) return; fa[px] =py ; //将x的父亲改为y} 连通块大小123456void merge(int x, int y) { int px = find(x), py = get(y); if(px == py) return; fa[px] =py ; //将x的父亲改为y siz[py] += siz[px];} 并查集按秩大小合并（启发式合并）12345678vector<int>siz(N, 1);//记录并初始化子集合的大小为1void uni ...

单点修改+区间求和123456789101112131415161718192021222324252627282930313233343536373839404142434445#include<bits/stdc++.h>#define endl '\n' using i64 = long long;using namespace std;signed main(){ std::ios::sync_with_stdio(false);cin.tie(0); int n, m; cin >> n >> m; vector<i64> a(n + 1); auto add = [&](int x, i64 k) -> void { for (int i = x; i <= n; i += i & (-i)) a[i] += k; }; auto query = [&](in ...

经典区间求和、区间修改1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677#include<bits/stdc++.h>#define endl '\n' using i64 = long long;using namespace std;struct segment_tree{ int L, R, size; i64 lazy, ans;} a[400010];signed main(){ std::ios::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; auto up = [&](int x) -> void { ...

逆元的应用场景——模意义下的除法 在模意义下，加减乘必然都是可行的，(ab)%p=((a%p) (b%p))%p ;但是除法是不可行的，(a/b)%p (a%p)/b 假设有个值inv[b],(即), 满足a / b = a inv[b]，即我们就需要找到满足binv[b]%p=1的b；根据费马的定理，如果p是个质数，则有%p=1, 即inv[b]= ，因此这样我们就可以把模意义下的除法改为乘法，需要用到快速幂（取模) Code(求):123456789101112131415161718192021222324#include<bits/stdc++.h>#define endl '\n' using i64 = long long;using namespace std;const int p = 1e9 + 7;i64 power_mod(i64 a, i64 b, i64 mod){ //快速幂取模 i64 res = 1; a = a % mod; while (b){ if (b & 1) res = (res * a) % mod; ...

素数筛（欧拉筛）1234567891011121314bool numlist[100000001];int prime[20000001], cnt;auto work=[&](int n) -> void{ for(int i=2; i <= n; i++){ if(numlist[i] == false) prime[++cnt] = i; for(int j = 1; j <= cnt && i * prime[j] <= n; j++){ numlist[i*prime[j]] = 1; if(i % prime[j] == 0) break; } }} 函数筛1234567891011121314auto getMu=[&]()->void{ mu[1] = 1; for (int i = 2; i <= n; ++i) { if (!flg[i]) p[++tot] = i, mu[i] = ...

采用阶乘逆元的相关知识，可以在预处理阶乘后以O(1)查询组合数，其中，p必须是一个质数123456789int C(int x,int y){ return 1ll*jc[x]*njc[y]%p*njc[x-y]%p;}for(int i=0;i<2;i++)jc[i]=njc[i]=inv[i]=1;//阶乘，阶乘逆元，逆元for(int i=2;i<=100001;i++){ jc[i]=1ll*jc[i-1]*i%p; inv[i]=1ll*inv[p%i]*(p-p/i)%p; njc[i]=1ll*njc[i-1]*inv[i]%p;}