Hexo

约数1约数，又称因数。整数a除以整数b(b≠0) 除得的商正好是整数而没有余数，我们就说a能被b整除，或b能整除a。a称为b的倍数，b称为a的约数。在大学之前，"约数"一词所指的一般只限于正约数。约数和倍数都是二元关系的概念，不能孤立地说某个整数是约数或倍数。一个整数的约数是有限的。同时，它可以在特定情况下成为公约数。 试除法求约数给定 n 个正整数 ai，对于每个整数 ai，请你按照从小到大的顺序输出它的所有约数。 输入格式第一行包含整数 n。 接下来 n 行，每行包含一个整数 ai。 输出格式输出共 n 行，其中第 i 行输出第 i 个整数 ai 的所有约数。 数据范围1≤n≤1001≤ai≤2×1e9 输入样例：123268 输出样例：121 2 3 6 1 2 4 8 代码个人代码123456789101112131415161718192021222324252627282930313233343536373839/* 首先我们要明确约数的定义 诺 a * b = c 那么 a,b便是c的约数。*/#include<bits/stdc++ ...

试除法判定质数给定 n 个正整数 ai，判定每个数是否是质数。 输入格式第一行包含整数 n。 接下来 n 行，每行包含一个正整数 ai。 输出格式共 n 行，其中第 i 行输出第 i 个正整数 ai 是否为质数，是则输出 Yes，否则输出 No。 数据范围1≤n≤100,1≤ai≤2^31−1 输入样例：123226 输出样例：12YesNo 代码个人代码1234567891011121314151617181920212223242526272829#include<bits/stdc++.h>using namespace std;// 数据范围的情况#define ll long longint main() { int m;cin>>m; while(m--){ ll val,i;cin>>val; // 特殊数据如1，2的情况 if (val == 1) { cout<<"No"<<endl; continue; } for ...

数学知识[TOC] 质数：题目连接 试除法判定质数:12345678//试除法判定质数还是很强的，可以判定很大的数是不是质数。bool IsPrime(int x){ if(x < 2) return false; for(int i = 2; i <= x/i; i++){ if(x%i == 0) return false; } return true;} 试除法分解质因数：123456789101112//分解质因数是除以所有可以整除的因子，并累计个数。最后的数如果不是1，就说明是质数void divide(int x){ for (int i = 2; i <= x / i; i ++ ) if (x % i == 0) { int s = 0; while (x % i == 0) x /= i, s ++ ; cout << i << ...

二分图 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。 二分图重要性质：没有奇数环染色法求二分图：时间复杂度：O(n+m)12345678910111213141516171819202122232425262728293031323334int n; // n表示点数int h[N], e[M], ne[M], idx; // 邻接表存储图int color[N]; // 表示每个点的颜色，-1表示未染色，0表示白色，1表示黑色// 参数：u表示当前节点，c表示当前点的颜色bool dfs(int u, int c){ color[u] = c; for (int i = h[u]; i != -1; i = ne[i]) { int j = e[i]; if (color[j] == -1) { ...

最小生成树Prim算法（用于稀疏图）：时间复杂度O(n^2+m)朴素版prim算法,一般应用于稀疏图,形式上和dijkstra算法很相似。初始化d数组，将1节点加入到最小生成树节点集合中。迭代n-1次，每次在S中寻找到T集合的最短距离，用这个节点更新其他非最小生成树节点。 12345678910111213141516171819202122232425// 设最小生成树节点集合为T，其他节点集合为S，vis数组用来标记该节点时候在T集合中// d数组保存的是每个点到T的最短距离int Prim(){ int res = 0; memset(dis,0x3f,sizeof dis); dis[1] = 0; for(int i = 0;i < n; i++){ int t = -1; for(int j = 1; j <= n; j++){ if(!vis[j] && (t==-1|| dis[j] < dis[t])) t = j; ...

最短路问题稠密图：m与n^2相当，使用朴素Dijkstra算法 稀疏图：m与n相当，使用堆优化版Dijkstra算法或SPFA算法 朴素dijkstra算法时间复杂度 O(n^2+m)123456789101112131415161718192021222324252627int g[N][N]; // 存储每条边int dist[N]; // 存储1号点到每个点的最短距离bool st[N]; // 存储每个点的最短路是否已经确定// 求1号点到n号点的最短路，如果不存在则返回-1int dijkstra(){ memset(dist, 0x3f, sizeof dist); dist[1] = 0; for (int i = 0; i < n - 1; i ++ ) { int t = -1; // 在还未确定最短路的点中，寻找距离最小的点 for (int j = 1; j <= n; j ++ ) if (!st[j] && (t == - ...

拓扑排序拓扑排序：在一个 DAG（有向无环图） 中，我们将图中的顶点（u，v）以线性方式进行排序，使得对于任何的顶点u到v的有向边（u，v）, 都可以有u在v的前面。 应用：可以判定一个图是否有环。 算法的实现过程： 先遍历所有的边，将所有入度为零的点加入到队列中。然后取出队头元素，对该元素连接的边进行扩展，如果该点的入度减1为0，就说明这个点一定在起点的后面，再次将该点入队，一直执行到队列为空为止。 模板: 1234567891011121314151617181920212223// 判断该图是否为有向无环图// 如果该图为有向无环图，top数组中的元素即为拓扑序列,d数组存储入度为零的点bool topsort(){ for(int i = 1; i <= n; i++){ if(d[i] == 0) q.push(i); } int cnt = 1; while(q.size()){ int t = q.front(); top[cnt] = t; ...

树与图的存储与遍历树与图的存储树是一种特殊的图，与图的存储方式相同。对于无向图中的边ab，存储两条有向边a->b, b->a。 (1) 邻接矩阵：g[a][b] 存储边a->b，所有边初始化为正无穷 (2) 邻接表： 123456789101112// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点int h[N], e[N], ne[N], idx;// 添加一条边a->bvoid add(int a, int b){ e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;}// 初始化idx = 0;memset(h, -1, sizeof h); 树与图的遍历时间复杂度 O(n+m), n 表示点数，m 表示边数。 深度优先遍历12345678910int dfs(int u){ st[u] = true; // st[u] 表示点u已经被遍历过 for (int i = h[u]; i != -1; i = ne[i]) { ...

模拟散列表维护一个集合，支持如下几种操作： I x，插入一个数 x； Q x，询问数 x 是否在集合中出现过； 现在要进行 N 次操作，对于每个询问操作输出对应的结果。 输入格式第一行包含整数 N，表示操作数量。 接下来 N 行，每行包含一个操作指令，操作指令为 I x，Q x 中的一种。 输出格式对于每个询问指令 Q x，输出一个询问结果，如果 x 在集合中出现过，则输出 Yes，否则输出 No。 每个结果占一行。 数据范围1≤N≤1e5−1e9≤x≤1e9 输入样例：1234565I 1I 2I 3Q 2Q 5 输出样例：12YesNo 个人代码ps 个人不会写哈希写了一个树凑合一下用吧(⊙﹏⊙) 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273#include<bits/stdc++.h>using namespace std;struc ...

堆排序输入一个长度为 n 的整数数列，从小到大输出前 m 小的数。 输入格式第一行包含整数 n 和 m。 第二行包含 n 个整数，表示整数数列。 输出格式共一行，包含 m 个整数，表示整数数列中前 m 小的数。 数据范围1≤m≤n≤1e5，1≤数列中元素≤1e9 输入样例：125 34 5 1 3 2 输出样例：11 2 3 个人代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748#include<bits/stdc++.h>using namespace std;const int N = 1010;int num[N],len = 0;// len 代表着最后节点的下标 len 去0 无意义 我们把一个节点的左右节点定义为 2*i 2*i +1void insert(int x) { num[++len] = x; int cur = len; // 插入点到末尾后需要不断和他的父节点 while(cur/2 != 0 &am ...