数论

题目链接：点我~~ 题意：求1e11内素数个数。 思路：Meisell-Lehmer的n^(2/3)方法，参考cf665F。 #include <bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define all(x) (x)....

题目链接：点我~~ 题意：n个有序序列的归并排序.每次可以选择不超过k个序列进行合并,合并代价为这些序列的长度和.总的合并代价不能超过T, 问k最小是多少。 思路：先对所有数排序，另外一个队列维护合并后的值，取值时从两个序列前端取小的即可。如果(n−1)mod(k−1)≠0，要把最小的(n−1)%(k−1)+1个数先合并一下。剩下的恰好可以每次合并k个数 #...

题目链接：点我~~ 题意：~~ 思路： 我们依次分析每一种棋子。 ①王。 首先注意一个3*3的棋盘，开始在(1,1)，问走到(3,3)谁有必胜策略。 穷举所有情况，容易发现这是后手赢。 对于N和M更大的情况，我们把横坐标每隔3、纵坐标每隔3的点都画出来，这些点都是符合后手胜的。 （因为无论先手怎么移动，后手都能重新移动到这些格子，直到到了终点） 如果初始点不...

题目链接：点我~~ 题意：~~ 思路：考虑一种暴力,每次枚举两两点对之间的曼哈顿距离,并开一个桶记录每种距离是否出现过,如果某次枚举出现了以前出现的距离就输 YES,否则就输 NO . 注意到曼哈顿距离只有 O(M) 种,根据鸽笼原理,上面的算法在 O(M)步之内一定会停止.所以是可以过得. 一组数据的时间复杂度 O(min{N^2,M}) . #inclu...

题目链接：点我~~ 题意：给你n个数，m个询问，每次询问某个区间，求这段区间所有数的gcd，然后问1~n所有连续区间中gcd的值等于区间所有数gcd的个数~~ 思路：对于求区间gcd可以用线段树维护，或者RMQ，因为后者的查询是O(1)~还是比较方便的。对于所有区间的gcd，考虑枚举左端点，二分区间进行预处理~例如12467，以1为左端点，1~5为右端点5个...

题意：求存在最大差值小于给定K值的区间段个数。 思路：利用RMQ求出区间最大最小值，再枚举右端点，二分区间找到满足要求的最大区间累加~~ #include <bits/stdc++.h> using namespace std; typedef long long LL; typedef unsigned long long ULL; t...

毕达哥拉斯三元组x^2 + y^2 = z^2 本原毕达哥拉斯三元组 gcd(x,y,z)==1 满足 x = m^2 – n^2,y = 2*m*n,z = m^2 + n^2,其中m>n 只需枚举m、n,然后将三元组x、y、z乘以i(保证i*z在所给范围内,因为z>x且z>y)。 #include<iostream&g...

给出一个x，求满足x = b^p，p最大是多少？ 直接枚举满足要求的p的个数，， 进行质因数分解也可以， x = p1^e1 * p2^e2 * p3^e3 ……. * pn^en p = gcd (e1,e2,…….en) #include<iostream> #include<cstdio...

哥德巴赫猜想~~ #include<iostream> #include<cstdio> #include<string> #include<string.h> #include<algorithm> #include<cstdlib> #include<ctime> #in...

用log10来求前N位 f(n)=n^k tmp=log10f(n)=klog10n tmp=tmp-floor(tmp) tmp=10^tmp //再放大相应的位数就可以了~ #include<iostream> #include<cstdio> #include<string> #include<...