令,0≤<,gcd(,)=gcd(+,).0≤x<m,gcd(a,m)=gcd(a+x,m).相等的个数等于,gcd(,)=gcd(,).,gcd(a,m)=gcd(x,m).然后欧拉定理一下就行了复杂度O(logm) #define ll long long inline ll phi(ll x) { ll ans = x, y = x; for (ll i = 2; i * i <= y; i ++) if (x % i == 0) { ans /= i, ans *= (i - 1); while (x % i == 0) x /= i; } if (x != 1) a...

分析题目性质，因为操作次数无限，所以可以把所有可以交换的位置放到一起处理，对于每一个这样的连通块，肯定要把大的放前面，小的放后面。用并查集处理连通块.然后同一连通块倒序输出，就可以得到字典序最大的解，复杂度O(nlogn). /** * struct Interval { * int start; * int end; * }; */ const int N = 1e5 + 10; int f[N], cnt[N]; vector<int> b[N]; int find(int x) { if(f[x] == x) return x; return f[x] = find(f[x]...

我们可以枚举因数来更新每个数字的中位因数里面小于等于 的那个。因为x最大为，因此只需要枚举到。然后暴力更新当前因数的倍数。这个复杂度是O(nlogn) const int mod = 998244353; long long f[1000010]; class Solution { public: /** * * @param x int整型 给定的x * @return int整型 */ int sum(int x) { // write code here for(int i = 1; i <= 1000000; i ++) for(long long j = i; j * i &l...

三角形两边之和大于第三边，因此不构成三角形的条件就是存在两边之和不超过另一边。所以就是贪心的使得尽量多的段能构成的总长度最小，即按照斐波那契数列的方法切割可以使得切割的段数最大，1，1，2，3，5这样可以使得任意三根木棒不能组成三角形，最后无法切割的部分加到最长的一根里面即可。 class Solution { public: /** * * @param a long长整型 木棒的长度 * @return int整型 */ int stick(long long a) { ull ans = 2; ull now = 1, sum = 2; ull x = 1, y = 1; if(a ==...

从左至右对区间进行排序，因为D满足单调性，即如果D可以，D-1一定可以。所以可以在分隔距离D上进行二分答案。对于固定的D，我们要检查是否可以放置至少N个玩偶。这可以通过贪心的策略来完成。只需将每个玩偶放在最左边的位置即可。一旦奶牛数量达到N，就可以break了，因此可以在O（N + M）时间检查一个D。所以复杂度为O（（N + M）log（max dist））。 /** * struct Interval { * int start; * int end; * }; */ #define LL long long #define INF 2000000000 #define X start #...

如果只考虑第k个序列，f[i][j]表示由i根棍组成的j高度开头的种类数即可。但是要求是波浪形，那么考虑加一维状态dp[i][j][0/1]表示用i根木棒，首位选择第j短的长度，类型为上凸或者下凹的排列数。(定义第二根比第一根长的为1，反之为0)。状态转换方程如下：dp[i][j][0] = sum(dp[i-1][k][1]) 其中k=j...i-1;dp[i][j][1] = sum(dp[i-1][k][0]) 其中k=1...j-1;边界初始化：dp[1][1][0] = dp[1][1][1] = 1;时间复杂度O() 空间复杂度 O(n) const int N = 20 + 5;...

考虑性质：每次运输的时间t是不变的所以T[i]表示运送前i个要用的时间,tot[i]表示在T[i]的时间内的最少次数。转移即可，记得先把所有冰激凌制作时间排序。 #define rep(i, x, y) for(int i = x; i <= y; i ++) class Solution { public: /** * 两个数表示答案 * @param n int整型 一次运输的冰激凌数量 * @param m int整型 总冰激凌数 * @param t int整型 一次运输的时间 * @param c int整型一维数组 表示每个冰激凌制作好时间<1e4 * @param c...

观察题目性质，发现交换的元素 mod K 相等，按照 mod K 进行分类后变成了相邻交换。那么在 mod K 意义下，不同的东西是独立的。所以拆成 K 个序列。答案是有多少对 i < j，使得 K | (j - i) 且 考虑这个东西怎么求，发现他就是一个顺序对（跟逆序对类似）的个数。那么可以用树状数组或者归并排序等方式直接做，复杂度O(nlogn)。或者考虑这个题字符串由小写字母组成，所以维护一下到当前位置的前缀数量即可，复杂度O(26*n)。 #define rep0(i, n) for(int i = 0; i < n; i ++) class Solution { pub...

今天已经Day4了，写个3天的总结吧。  Day1  先说说考试：  T1  这题大新闻了，样例搞错、数据范围没写全。  然后我前一个小时都是一脸懵逼的状态，老师在1h30min左右更新的。瞬间秒掉。。。dp+矩阵乘法。  T2  这题显然最长路吗，优化个建图。优化了许久。。算了，写个暴力算了。暴力一码，扔那里了。结果题目有个坑，就是高度是0但价值不是0的时候也可以走2333。然后因多组数据悲惨爆0。。  T3  看着貌似有规律啊。找找规律，好吧，没找到，GG。交暴力。。  130滚粗，（但居然还是rank1？） 下午讲课，小清新的博弈论，都听懂了，好开心。就是题目好多啊。慢慢刷吧。。

真的好久没写博客了。  最近我都在随着一群进队爷们准备国赛。  并参加了网络同步赛。虽然暂时没出成绩，但自我感觉良好啊。  最近一段时间，开始刷题，博客将会持续更新。  望神犇们留个友链啊

Description Due to recent rains, water has pooled in various places in Farmer John’s field, which is represented by a rectangle of N x M (1 <= N <= 100; 1 <= M <= 100) squares. Each square contains either water (‘W’) or dry land (‘.’). Farmer John would like to figure out how many ponds ...

Description Phorni 是一个音之妖精,喜欢在你的打字机上跳舞。  一天,阳光映射到刚刚淋浴过小雨的城市上时,Phorni 用魔法分裂出了许多个幻影,从 1 到 n 编号。  她的每一个幻影都站在打出的字符串的一个位置上,多个幻影可以站在同一个位置上。  每一个幻影代表的字符串即为从它站立位置开始的后缀,注意站立位置是从右往左数的。  让我们形式化地描述一下,若第 i 个幻影站在 Pi 上,那么它所代表的字符串就是 S[L-Pi+1…L],其中 L 是字符串 S 的长度。  每一次,她会选一段编号区间 [l..r],而编号在这个区间中的幻影中,字典序最小的一个将跳一支舞,若有多个...

Description 给一个长度为n的序列a。1≤a[i]≤n。  m组询问，每次询问一个区间[l,r]，是否存在一个数在[l,r]中出现的次数大于(r-l+1)/2。如果存在，输出这个数，否则输出0。 Input 第一行两个数n，m。  第二行n个数，a[i]。  接下来m行，每行两个数l,r，表示询问[l,r]这个区间。 Output m行，每行对应一个答案。 Sample Input  7 5 1 1 3 2 3 4 3 1 3 1 4 3 7 1 7 6 6 Sample Output  1 0 3 0 4 HINT 【数据范围】 n,m≤500000 Source By Dzy 主...