51nod1217
N个不同的数a[1],a[2]...a[n]，你可以从中去掉K个数，并且找到一个正整数M，使得剩下的N - K个数，Mod M的结果各不相同，求M的最小值。(n <= 5000, k <= 4, a[i] <= 1e6)
预处理出任意两个数的差，用cnt[u]记录有多少对的差为u，则模m下同余的对数 = cnt[0] + cnt[m] + cnt[2 * m] + cnt[3 * m] + ...
从小到大枚举m，当模m下同余的对数 > k * (k + 1) / 2时显然无解，否则把这些同余的数字挑出来，看要去掉几个数字，和k比较，看m是否合适
51nod1742
一个含有平方因子的数被称为有趣的数，令f[x] = (n的约数中有趣的数的个数)，给区间[a，b]，求∑f(i)（i取遍[a, b]中的数字）(a, b <= 1e9)
想到莫比乌斯函数为0表示这个数有平方因子，故 1 - |mu[x]|为1表示这个数是有趣的数，大概化一化公式，即要求莫比乌斯函数绝对值的前缀和。
当n <= 1e7时，可以线性筛预处理，否则可以容斥原理求出1～n中有趣的数的个数，其中只需要利用莫比乌斯函数作系数就行了。
51nod1537
问 (1 + √2) ^ n 是否能写成 √m + √（m - 1）的形式，n <= 1e18， m对1e9 + 7取模。
注意到(1 + √2) ^ n可以看成是二阶递推数列的一部分，且n的数据范围很大，以及要取模，多半会是矩阵快速幂
a[n] = (1 + √2) ^ n + (1 - √2) ^ n，则 a[n] = 2 * a[n - 1] + a[n - 2]。
向题目靠拢，令 (1 + √2) ^ n = x + y√2，则 (1 - √2) ^ n = x - y√2
则 a[n] = 2 * x，将上面的二式相乘，x * x - 2 * y * y = (-1) ^ n，则可以求出y，再判断一下就行了。
51nod最小集合
给你一个数字集合，你知道其中n个数字，已知这个这个集合任意两个数字的最大公约数也在这个集合中，求这个集合最少的元素个数？
(n <= 1e5, a[i] <= 1e6)
看到a[i]的数据范围，大概是从大到小枚举每个数字是否出现，用vis[]标记是否存在，怎么判断是否存在两个k的倍数的最大公约数是k？
看的题解，将所有k的倍数求最大公约数，如果它等于 = k，就存在k...
51nod1379
Fib[0] = 0, Fib[1] = 1, Fib[n] = Fib[n - 1] + Fib[n - 2]
令Sor[n] = Fib[0] | Fib[1] | Fib[2] ... | Fib[n]， 求Sor[n] (有Q组(<= 10000)，n <= 1e10)
水题
首先 Fib[n] < 2 * Fib[n - 1] (n > 2)， 那么意味着Fib数列会递增，但每次至多前移一位，将1～n中的Fib作或运算就会把所有位都填成1，只需要知道Fib[N]的位数即可，通过对通项公式取对数即可确定位数。
51nod1436
求解数对m取模的结果。 (n <= 1e18, k <= 1e18, l <= 64, m <= 1e9 + 7)
将k写成二进制数后，令len表示这个二进制数的长度，若len > l，特判结果为0
否则逐位考虑，最后根据乘法原理相乘
即要求长度为n的01序列中没有连续的1的序列数，这个是可以递推的，考虑最后一个数字，F[n] = F[n - 1] + F[n - 2]，
51nod1439
n个数字a[1], a[2], a[3], ... , a[n]，一个空集合，每次操作是向集合加一个数字或删一个数字，每次给你一个x，如果a[x]在集合中，则删去a[x]，否则加入a[x]，求每次操作后的集合中互质对数(n <= 2e5, a[i] <= 5e5)
首先我们只需要求当前操作会增加／减少多少互质对数，令y = a[x]，即集合中有多少数与y互质，枚举y的约数，通过莫比乌斯函数判断增减(就是容斥原理)，并且更新cnt[u](u的倍数的个数)，q√n的时间复杂度，注意当y = 1时需要特判一下
cf846F Random Query
给你n个数字，然后你随机挑一个区间，求这个区间不同的数的个数的期望值(n <= 1e6, a[i] <= 1e6)
水题，显然 dp[i]可以表示前i个数字的不同的数的个数的期望值，dp[i] = dp[i - 1] * sqr((i - 1) / i) + 1.0 / sqr(i) + 2 * sum / sqr(i)
sum 可以 dp时更新出来
cf837E Vasya's Function
f(a, 0) = 0
f(a, b) = 1 + f(a, b - gcd(a, b))
显然一个d可能被减去多次，那么你一次把要减去多少个相同的d算出来就好了，即令 b - k * d = i * t，i是d的倍数，同时满足b - k * d最大，枚举a的约数即可，注意一下一些特殊的情况就可。递归实现。
cf869C The Intriguing Obsession
有红蓝紫三种颜色的点，分别有a，b，c个，你需要连一些边，使得同一个颜色的点或者不联通或者最短路大于等于3，求方案数？
为了满足上述条件，必须满足1.同一种颜色的点没有连边，2.一个红点至多连一个蓝点和一个紫点
显然任意两个颜色间的点是不影响的，对于某两类颜色，你枚举有多少条边，再枚举子集和排列。
cf663A 给你一个表达式，比如 ？ + ？ - ？ - ？ = n，其中只有加减，并且只知道等式右边的值n和左边的加减号顺序，左边最多有100项且每一项不超过n，求解。
水题，先考虑极端情况确定方程是否有解，然后再从极端情况(比如最大)向解调整。。肯定能得到答案。
cf258C Little Elephant and LCM
给你一个数列a[1], a[2], a[3], ... , a[n]，确定有多少个序列b满足。(n <= 1e5, a[i] <= 1e5)
1. b[i] <= a[i]。2.LCM(b[1], b[2], ..., b[n]) = max(b[1], b[2], ... b[n])。答案对1e9 + 7取模
首先，对一个合法的b序列，b[i] | max(b[1], b[2], ..., b[n])，故只需枚举最大的数来计算方案
按约数从小到大的顺序枚举，看每两个约数间有多少个数，然后乘法原理，再减去不存在最大数的情况
cf145C Lucky Subsequence
一个数如果只由4，7组成，称为幸运的数，给你由n个元素组成一个数列a，让你挑出k个数，使得其中每个幸运的数最多出现一次，不幸运的数随意，求方法个数(k <= n <= 1e5）（方案不同只要存在选择的数下标不同）
显然这是一个分组背包问题，每一个幸运的数放一组，不幸运的每一个数都单独设一组，但这样n^2显然不行
观察到幸运的数是1020个，所以真实只用考虑这1020个背包，做一次dp
然后枚举选择用了多少个不幸运的数，然后组合数，乘法原理balabala....
cf223C Partical Sum
给你n个数字，每次对原数列求前缀和，作为新数列，求k次后的数列
和多校时一道题挺像
cf439E Devu and BirthDay Celebration
有q组询问，每次给你n，f，问x1 + x2 + x3 + ... + xf = n，其中gcd(x1， x2， x3, ... , xf) = 1
(q <= 1e5, f <= n <= 1e5)
对于每个n，枚举它的约数d，求x1 + x2 + ... + xf = n ／ d的解，然后容斥一下就可以了
cf204C 懒得写了2333
cf32C 有一个网格中有一只跳蚤，他每次能跳s步，可以跳任意多次，并且同一个格可以跳多次，对于一个格如果他能到达的格最多，我们称它为好格，问有多少个好格？
水题，先算算(1, 1)能到达多少个格，然后看有多少个类似(1, 1)的格
LL a = (n - 1) / s;
LL b = (m - 1) / s;
LL ans = (a + 1) * (b + 1);
LL x = n - a * s;
LL y = m - b * s;
ans = ans * x * y;
cf336D Vasily the Bear and Beautiful Strings
对一个由n个0，m个1组成的字符串，可以进行如下操作
如果最后两位为0，将最后两位替换为1；否则替换为0
在进行若干次这样的操作后，只剩下字符g。
给定n，m，g，求满足条件的字符个数？
有如下递推公式
solve(n, m, 0) = C(n + m, m) - solve(n, m, 1) //显然等于总数减去最后剩下1的
solve(n, m, 1) = solve(n - 1, m, 0)。 //操作若干次剩下两个0
cf225E Unsolvable
对于 z = x ／ 2 + y + x * y ，将不存在正整数解的z从小到大写出来，求第n个z是多少，对 1e9 + 7 取模
将x按奇偶分类，得出z具有哪些性质
令 x = 2 * x1 + 1, z = x1 + y + (2 * x1 + 1) * y => z + 1 = (2 * y + 1) * (x1 + 1)
可以看出 z + 1 中不能有素因子，故 z + 1 = 2 ^ t，即 z = 2 ^ t - 1
令 x = 2 * x1，z = x1 + y + 2 * x1 * y，两边同乘2，=> 2 * z + 1 = (2 * x1 + 1) * (2 * y + 1)
即 2 ^ (t + 1) - 1 不能有素因子， 故问题就是找出若干个梅森素数。。。感觉不上网查梅森素数表根本不能做啊QAQ
cf396B On Sum of Fractions
令 p(i) = 不超过i的最大素数，q(i) = 严格大于大于i的素数
求 for (i = 2; i <= n; ++ i) sum += 1 / (p[i] * q[i]) 输出最简分数
显然可以裂项，故只需要快速判定素数即可，使用mille-rabin算法
cf83B
有n个病人，他们刚开始按1，2，...，n排队，每个病人要看 a[i] 次病，对每个病人，看完一次病后，如果他已经看完所有次后，他离开队伍，否则他排在队伍的最后边，求医生看了k次病后的排队队列？
(n <= 1e5, a[i] <= 1e9, k <= 1e14)
水题，考虑医生已经看了几轮病了，那么此时看过多少个人具有单调性，二分看病轮数，再模拟一遍。。就好了
cf402E 给你一个矩阵O，问是否存在整数k使得O ^ k中的所有元素都大于0。(矩阵大小不超过2000 * 2000)
水题，等价于问这样一个有向图是否强连通，那么只需要看1是否能到达其他所有点以及其他所有点是否都能到达1
cf632D 给你n个数字和m，要求你找最多的数字使得它们的LCM不超过m(n, m <= 1e6)
枚举公倍数，统计有多少个数整除它，最多的那个就行了。
cf229C 给你一个有n个点的完全图，每条边或者染红或者染蓝，求同色三角形个数
同色三角形个数 = C(n, 3) - 异色三角形个数
异色三角形个数 = 异色角个数 ／ 2
cf235B 以后写
rep(i, 1, n) {
dp[i] = dp[i - 1] + p[i] + 2.0 * t1;
t1 = (t1 + t2) * p[i + 1] + (1 - p[i - 1]) * p[i] * p[i + 1];
t2 = t2 * p[i + 1] + (1 - p[i - 1]) * p[i] * p[i + 1];
}
cf255D
初始给你一个n*n的白色网格图，然后给你一个(x, y)被染成黑色，每一秒黑色的格会向四周扩散，问第多少秒会有超过c个黑色方格？
二分答案，计算的时候可以按照容斥原理计算有多少个被染成黑色。
cf431D
求一个数字n，使得[n + 1, 2 * n]之间有m个数字在二进制下恰好有k个1
注意n， n + 1， n + 2，....，2 * n - 2
n + 1， n + 2，...，2 * n - 2， 2 * n - 1， 2 * n
其中2 * n 是 n 后面补0得到的，所以以n + 1 为起点大于等于以n为起点的，具有单调性
然后二分答案+数位dp
cf257D 水题