题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3579      1 #include <iostream>  2 #include <algorithm>  3  4 typedef long long LL;  5  6 using namespace std;  7  8  9 10 11 LL ex_gcd(LL a,LL b,LL &x,LL &y){ 12 if (b == 0){ 13 x = 1; 14 y = 0; 15 return a; 16  } 17 LL gcd = ex_gcd...

中国剩余定理，又名孙子定理   能求解什么问题呢？ 问题： 一堆物品 3个3个分剩2个 5个5个分剩3个 7个7个分剩2个 问这个物品有多少个    中国剩余定理给出了以下的一元线性同余方程组：           中国剩余定理说明：假设整数 m1, m2, ... , mn两两互质，则对任意的整数： a1, a2, ... , an，   方程组(S)  有解，并且通解可以用如下方式构造得到：   设     是整数 m1, m2, ... , mn的乘积，并设     是除了 mi以外的 n- 1个整数的乘积。   设     这个就是逆元了          通解形式为       在模...

题目链接：https://cn.vjudge.net/contest/319720#problem/B   题意：给出两个数 n、c，求从 1~N 的素数序列，若素数个数为奇数，则输出序列中心的 2*c-1 个素数，若为偶数，则输出序列中心的 2*c 个素数。若 c 大于素数个数，则输出整个序列。 思路： 打表求素数，再计算序列中心位置，然后判断奇偶输出即可。注意这里的序列中心的意思（ = = 一开始理解错了） 然后这题让我掌握一下如何输出序列中心的方法吧。     1 #include<iostream>  2 #include<cstdio>  3 #include...

题目链接：https://cn.vjudge.net/contest/319720#overview   题目大意：输入两个数L和U(1<=L<U<=2 147 483 647)，要找出两个相邻素数C1和C2(L<=C1<C2<=U)是距离最小的，如果相邻素数不止一对，选择最初的，还要找出两个相邻的素数D1，和D2是距离最大的（同样在有多对的情况下选择最初的） 其中L<U，L和U的差不超过1 000 000 输入样例： 2 1714 17 输出样例： 2,3 are closest, 7,11 are most distant.There are no...

 题目链接：https://cn.vjudge.net/contest/318888#problem/M       思路：      1 #include <stdio.h>  2 #include <iostream>  3 #include <algorithm>  4 #include <string.h>  5 #include <stdlib.h>  6 #include <math.h>  7 #include <queue>  8 #include <set>  9  10 #def...

题目链接：https://cn.vjudge.net/contest/318888#problem/L   思路：      1 #include <stdio.h>  2 #include <iostream>  3 #include <algorithm>  4 #include <string.h>  5 #include <stdlib.h>  6 #include <math.h>  7 #include <queue>  8 #include <set>  9  10 #define I...

题目链接：https://cn.vjudge.net/contest/318888#problem/K   题意： 给你n个字符串，求至少出现在向上取整n/2的个串的公共子串如果有多个就输出多个。   思路：      1 #include <stdio.h>  2 #include <iostream>  3 #include <algorithm>  4 #include <string.h>  5 #include <stdlib.h>  6 #include <math.h>  7 #include <que...

题目链接：https://cn.vjudge.net/contest/318888#problem/J   思路：      1 #include <stdio.h>  2 #include <iostream>  3 #include <algorithm>  4 #include <string.h>  5 #include <stdlib.h>  6 #include <math.h>  7 #include <queue>  8 #include <set>  9  10 #define I...

其实大致的步骤和正数快速幂是一样的，只不过它是矩阵。     1 #include <stdio.h>  2 #include <iostream>  3 #include <algorithm>  4 #include <string.h>  5 #include <stdlib.h>  6 #include <math.h>  7 #include <queue>  8 #include <set>  9 10 #define INF 0x3f3f3f3f 11 #define pii pair...

题目链接：https://cn.vjudge.net/contest/318888#problem/I   题意： 求两个字符串的最长公共子串并且输出   思路： 和求最长公共子串的思路是一样的，就是多一个记录位置的操作。     1 #include <stdio.h>  2 #include <iostream>  3 #include <algorithm>  4 #include <string.h>  5 #include <stdlib.h>  6 #include <math.h>  7 #include &...

题目链接：https://cn.vjudge.net/contest/318888#problem/H   题意： 求两个子串的字符串的最长公共子串   思路： "最长公共子串"解法(摘自罗穗骞的国家集训队论文): 字符串的任何一个子串都是这个字符串的某个后缀的前缀。 求A和B的最长公共子串等价于求A的后缀和B的后缀的最长公共前缀的最大值。如果枚举A和B的所有的后缀， 那么这样做显然效率低下。 由于要计算A的后缀和B的后缀的最长公共前缀， 所以先将第二个字符串写在第一个字符串后面， 中间用一个没有出现过的字符隔开，再求这个新的字符串的后缀数组。观察一下，看看能不能从这个新的...

题目链接：https://cn.vjudge.net/contest/318888#problem/F   题意： 求重复次数最多的连续重复字串，并输出   思路： 这题其实和求重复次数最多的连续重复字串输出其出现次数 的思路是差不多的。 我们首先先将满足要求的长度都存起来 我们知道后缀数组sa[]就是根据字典序大小来排序的，故可以借用sa[]数组找出最先符合重复次数的子串即为所求 输出子串可以通过在要输出的段的末尾赋为'\0'，这样只要printf时调输出段的开头就可以了，因为'\0'人工标记了字符串结束      有人可能会疑惑为什么if 是Max-1 而里面就变成了Max 这里可以去看上...

题目链接：https://cn.vjudge.net/contest/318888#problem/G   题意： 给定一个字符串，求重复次数最多的连续重复子串   思路： 我们先看下罗老师的论文中给出的思路    虽然话很短，但是很难理解。我就讲一下我刚开始无法理解的一些地方吧，既方便我巩固也方便我今后复习。   1、为什么连续出现了K/L+1次？ 我们先看这个图片上的例子 r[6] :  a a b a a b a a b a b r[9] :  a a b a a b a b 先考虑往后匹配可以知道K=9，K/L只是在 r[9]之后重复出现的次数 再加上 r[6]->r[9]之间重...

题目链接：https://cn.vjudge.net/contest/318888#problem/C   题意：给定一个字符串，求不相同的子串个数。   思路： 感觉就是记住这个公式吧。。至于怎么推出来的我也不知道。。。。    如果有大佬知道怎么推出来的欢迎在底下给我留言      但是这里有一个点需要小心： 因为我们求后缀数组的时候为了防止越界的问题的话，会让最后一个为0(一个最小的从未出现的值)。这样的话我们的末尾会多一个0，所以如果是这样我们推出来的公式应该是 (n-1)-sa[k]+1-height[k]       1 #include <stdio.h>  2 #i...