线性筛一般是接近线性的速度去进行素数筛，所以时间接近O(n) 而线性筛的原理是处理掉埃筛的不完美问题，即使被重复筛选过的数只被筛选过一次 而每个大于等于2的数都具有的特性是每个数都可以分解为n个素数相乘，即唯一分解定理。   结合代码实际来看：  const int N = 20010; int cnt = 0;//素数个数 int prime[N];//素数集合 bool ispri[N] = {true, true};//素数的判定集合，0和1不是素数 void EulerPrime(){ for(int i = 2; i < N; i++){ //如果是素数，放入素数集合中 if(...

超棒的欧拉函数讲解：https://blog.csdn.net/ydd97/article/details/47805419 下面的大部分都是借鉴这位大佬的，加了点自己的理解。   我就比较懒，直接贴代码了。（讲解都在注释中）  /* 欧拉函数的作用：用于求小于n的与n互质数的个数 欧拉函数的公式： φ(n)=n*(1-1/p1)*(1-1/p2)*(1-1/p3)*(1-1/p4)…..(1-1/pn), 其中p1, p2……pn为n的所有质因数，n是不为0的整数。φ(1)=1（唯一和1互质的数就是1本身）。 1-1/pi = (pi-1)/pi */ const int N = 10001...

题意：给你数n和d，让你求小于n的数中，以d作为最大因子的数有多少个。 我们简单分析可得，这个数范围必定是 d + 1到n - 1。   本题刚开始就会被数据范围所限制，开1e9的数组显然不行，而这题作为一道练习题想到了线性筛。 但是不管怎样开1e9的数组是不合理的，所以就分析题意，果然，d作为数的最大真因子有 d * x = num（<n） 且x一定是个大于1的质数，即x一定是数的最小质因子，那么我们可以得到x的范围 即x <= d 且 x <= (n - 1) / d 即xmax = min(d, (n - 1) / d);   那么我们只需枚举小于等于xmax的素数即可...

哈希表是一种非常带劲的存储方法，它将一定个数内的数据以一种降低数据规模的方式存储着，哈希表的主要操作就是添加数据和查找数据，当然你也可以用标记来标记数据是否被删除（实际上，它只是被你标记删除了，并未被实际删除并释放内存）   上模板题让我们直观感受下： Acwing840 模拟散列表：传送门 ：https://www.acwing.com/problem/content/842/ 这题就让我们实现了哈希表的存储和查找： 比较好用的两种方法：拉链法和开放寻址法   1.拉链法 一个节点上存储着 取模后位置相同的数据，由于存储位置相同，为避免矛盾，采用拉链法将其以拉链形式展开存储 首先创建存储位置...

存储： 如a与b之间的边的存储 1.有向图。如果给出边的方向为a→b，则建立一条由a指向b的边即可 2.无向边。给出两点a与b之间存在一条边，则a→b和b→a全部成立，那么我们需要建立一条由a指向b的，一条由b指向a的边。   存储具体实现方式：一、使用邻接矩阵。 开二维数组以二维数组的两个下标指定边的指向，二维数组的初始化为-1，数组元素的值代表边的权重。但这种方法可能会浪费大量空间。   二、使用邻接表。 开一个一维数组记录每个点，以他们作为头结点作单链表存储与该点存在边的所有点。 更常用的是邻接表，较为省空间。   遍历：每个点只会被遍历一次。无需刻意从某个点开始遍历，因为树是无环连通图...

传送门：https://blog.csdn.net/qq_41713256/article/details/80805338

C++STL中默认的优先队列是大根堆，即父结点总是比子结点大。 那么priority_queue<int> PQ即声明一个int型大根堆 如果想要声明一个小根堆则需要这么声明priority_queue<int, vector<int>, greater<int> > pq。 我们知道堆的模型就是完全二叉树（定义看不懂的自行补课） （完全二叉树：如果二叉树的深度为k，则除第k层外其余所有层节点的度都为2，且叶子节点从左到右依次存在。也即是，将满二叉树的最后一层从左到右依次删除若干节点就得到完全二叉树。满二叉树是一棵特殊的完全二叉树，但完全二叉树不...

输入字符(%c)https://blog.csdn.net/qq_41282102/article/details/80246701 输入字符串(%s)   注意：之后单个字符可以使用char op[2]用char输入，多个字符还是老老实实用%c中间手动用空格做分隔符

https://blog.csdn.net/qq_40772692/article/details/81872831

即对增广矩阵进行初等行变换，将其转换为行最简阶梯形矩阵 AX = B与C(标准型)X = D是同解方程组。 来看算法实现过程： 有矩阵我们来进行初等行变换 一、先来枚举每一列： ①枚举第一列 1.找到第一列中绝对值最大的一行，这里即2 1 -3 -9这行 2.将绝对值最大的一行与第一行交换得到 3.将第一行第一个数变为1，得到 4.将下面所有行的第一列消成0，得到 这时候第一行已经固定了，所以接下来我们要从第二行开始的其他不固定的方程中寻找到第c列中绝对值最大的行。   ②枚举第二列 1.找到第二列中绝对值最大的一行（注意此时第一行已经固定，因此我们只能从第二行开始寻找）即0 3/2 1/2 ...

这里默认两方均采取最优策略 1. 尼姆博弈 n堆石子，每堆的数量a1，a2，a3...an，一方取完后石子个数为0则该方获胜，问先手是否必胜 if ans = a1^a2^a3^...^an ≠ 0 先手必胜 else 先手必输   延伸1：在此问基础上添加一个集合，集合内的数字是每次操作可取的石子个数，每次从一堆中取，最后无法取者判输 对每堆石子算得其sg函数，sg函数异或后不为0，则先手必胜 否则先手必输   延伸2：在此问基础上添加一个条件：每次从不超过k堆中取任意多个石子，最后无法取者判输（Moore' s Nimk） 将每堆石子数换算为二进制，计算出二进制中每位的个数x mod (k...

比赛的时候想的是尽量先炖鱼，果然还是赛后牛逼，反应过来无论怎样总时间内一定有所有的炖鱼时间，所以只需要尽量缩减我们的钓鱼时间即可。 一、在炖鱼时间内可以把所有鱼都钓上来，那ans = k + t[1~n] 二、不能在炖鱼时间内把所有鱼都钓上来 即每次钓一条鱼上来后，鱼都会煮过。 如钓鱼时间为2，炖鱼时间为1，钓鱼上来后，炖的鱼煮过了1分钟。 而钓鱼时间为2，炖鱼时间为3，钓第一条鱼上来后，鱼还没煮熟，钓第二条鱼后才煮过1分钟，因此这时候可以在炖鱼时间内不花多的时间钓上来至少一条鱼。   由于我们可选择钓上来的鱼的先手顺序，因此我们可在煮鱼时间在x = (1~k-1)内尽量大的鱼中选择，即选择k...

算是学了下map的用法 题意就是找到最多的中心点，然后剩下就是得到没有匹配到最多中心点的数，这就是需要添加的点数  #include<bits/stdc++.h> using namespace std; typedef pair<int, int> PII; typedef map<PII, int> MII; MII::iterator iter; const int N = 1010; PII p[N]; MII M; int n; int main() { scanf("%d", &n); for(int i = 1; i...

题意： 擅长唱跳rap篮球和music的kunkun也“擅长”排队，每个球员都有已知的能力值，同时kunkun的附加光环使得每个队员对于其后面的人都有附加能力值m，即对于和后面的人比较的时候，他们都在已知能力值上加上m，但是有的队员对这种排名并不满意，所以他们想知道在有附加能力值的情况下，他们与后面队员中比他们能力值大或者相等的队员中最多隔了几个队员。 即求对于，使得  中得到的最大的（>=0）最大为多少，若不存在则输出-1。 题解：单调队列+二分 参照官方题解的，先从排名最后的队员开始从后向前构造一个单调递增队列，序列中存储着能力值索引，当某个数小于等于队尾，那么二分得到最小的大于等于...