之所以写这个题是因为他提供了一种新的解决问题的思路。。两个暴力算法结合起来竟然就不暴力了。。
首先直接暴力枚举每个set里的余数然后解同余方程组可以得到一个Πki复杂度的算法，但是这个在k太大的时候会爆，然后k很大的时候就用了同余方程的另一种暴力解法，找到一个同余方程枚举他的所有解然后去判断其他的等式是否满足。。。这个在k比较大的时候比较快（但是感觉这俩算法组合还是有点看RP
代码基本上都是抄的书上就这。不过调了下LIMIT的范围发现从100到500000都可以过。。
[数学][差分数列][数学归纳法][模拟] LA4119 Always an integer
题意：给出一个多项式，判断它是不是在所有整数点都取值为整数。
一个屌丝做法就是可以每次都随机数，只要数量足够一定可以把非整数判断出来。正解是利用数组差分的操作和取模的性质，自己想真的想不到。。
其实如果考虑思考方向的话，对于数据，一开始的思路应该是，既然有100个阶那肯定不是用某种解析的方式去做，而是选择一些点代入判定。这样的话问题变成了代入哪些点。首先如果分母上的数字比较小，那么可以算0-D之间的所有数字，但是D也很大，就没办法这么算了。这时候可以发现唯一可操作的只有阶的数量，然后就应该往这个方面去想了。。。当然这个数学归纳法的差分确实是有难度的，很难想到。。
沈阳赛得来的教训：模拟一定要在纸上写好所有情况再敲代码。。。
[母函数][容斥][FFT][模板] SPOJ TSUM Triple Sums
https://cn.vjudge.net/problem/SPOJ-TSUM
跟焦作选拔的时候那个题目的思路完全一样，用母函数可以考虑到所有的情况，然后去掉三个重复的和两个重复的再除以6就得到了去重后的结果。
收获主要是发现了FFT那个乘法的操作可以全部在一次循环里完成。。。神奇。。还有就是移位操作可以避免复数，而输出的时候记着要移回去原位。 继续阅读“[母函数][容斥][FFT][模板] SPOJ TSUM Triple Sums”
[母函数][容斥][FFT] UVa 12633 Super Rooks on Chessboard
一开始看了很久不知道怎么求被对角线覆盖到而没有被横纵覆盖到的格子数，后来忽然发现可以把没被占用的横纵坐标标记为1啊！这样两个卷积起来就是没有被横纵占用的对角线上的格子数量了！！！然后遍历每条对角线，如果被覆盖到了就减去这上面没有被横纵覆盖到的格子！
wa点：日常LL，以及他这个操蛋的横纵坐标标识法，有点难受，得把棋盘左右反转一下才好做。
[数学][大整数质因数分解] codeforces1033D Divisors
思路简单，就是求出来结果的所有质因数的指数+1乘起来就行了。
首先由于题目的要求这里读入的ai只有两种情况，要么ai=p*q是两个不相等素数的乘积，要么ai=p^k，其中k取2，3，4。显然后一种情况很容易处理，但是第一种就有些难受了，直接的想法是用一些优秀的O(N^(1/4))的非完美大整数分解算法（这个看tutorial的评论区神仙各有千秋）。但是由于第一类的数只能分解成两个质因数，而且我们最后要的是质因数的指数而不需要关心质因数本身是多少，所以就有了更好的策略：如果一个数字的质因数在其他数字中出现过，那么一定可以通过gcd求出来，这时候等于说另一个质因数直接一除也能求出来，等于这个ai就完全解决了，像第二种情况一样加到map里即可；如果说这个数的俩质因数都没有在其他数字中出现过那么我们肯定不能求出来这俩数字是多少了，但是我们可以知道出现了俩独特的质因数，他出现且仅出现在所有aj==ai里，那么我们可以把ai直接存进map里，存起来他对应的加了多少次，另外要单独开一个set记录下来哪些ai是这样的ai，最后计算的时候如果是这样的ai的话就乘以(1+map值)的平方就可以了。
所以说一定要分析所给数据的性质，他的约束是解题的难点但同时也可能是解题的突破口。
写的时候还有一点弄错了就是把哥德巴赫猜想和这个搞混了。。那个是+这个是*，而且哥德巴赫猜想在1e18的范围内一定是有一个小的和一个大的，这个小的不超过1e5好像，所以那个是只需要枚举小的然后判断大的是否为质数即可。
[拓扑序][博弈][重点错误] codeforces 1033C Permutation Game
这个题wa到最后才意识到是dfs刷表的思想本身是错误的，必须按照拓扑序来处理，这两个是不等价的。不等价的原因是dfs可能会多次刷到同一节点而且这个节点的父节点还没有完全确定下来。比如当某个节点只有一个父节点的时候，本来dfs给了他1，也就是必胜态，但是如果某一次之后的刷新把父节点变成了1，那么由于该节点只有一个父节点所以他只能变成0。而原来写的dfs不能解决的就是这样一个问题：对于一个节点来说，是不是所有的父节点都是1或者至少有一个0，因为单纯的dfs可能会求很多遍这个点（如果不这样又没办法更新），如果用拓扑序的话就可以保证在搜到一个点的时候这个点的父节点已经全部搞定了，这也跟拓扑序处理的时候每次只走“一步”有关系。这样的话就可以保证不会有多余的1没有变成0了。
[数学][思维] 2018camp day1 Board
http://newoj.acmclub.cn/problems/2054
题目给了一个方块板子，每次要么给同一列所有数字加上同一个数，要么给同一行加上全一个数，然后现在给出经过若干次这种操作之后的一个局面但是把其中一个点换成了-1，要求出来这个点的值应该是多少。
一开始没什么思路，后来写了写表达式似乎发现了可以直接解出来。设ri是第i行加的总数字，ci是第i列加的总数字，row是现在的-1所在的一行的和，col是-1所在的一列的和，若-1坐标为x，y，则可以设要求的数字为t=rx+cy，这时候可以列出来两个方程：
① row+col+2t+21==nt+Σri+Σci
② n*(Σri+Σci)==t+1+Σboard[i][j]
其中第一个方程是要求的那一点的行和列的和的两种表达式，第二个方程式整个board上的所有的点的和的两种表达形式。如果把(Σri+Σci)看作一个整体消掉，可以直接求出来t的表达式t=(n*(row+col)+2*n-Σboard[i][j]-1)/(n-1)^2
[学习] 线性筛+预处理+遍历/分解质因子
写这个是还是从今天那个C题目来的。看正解的时候发现了他用了一个很神奇的遍历质因子的方法，没有多余的操作，就是完全的遍历每一个质因子，只不过需要预先用线性筛处理出来1到n的每一个数字的最小质因子。感觉适用于需要分解多个数字质因子的情况但是我自己写的暴力sqrt(n)貌似也不慢多少就很迷。。。emmmmmm不管了先记下来再说。
[数学][质因数分解][预处理优化] codeforces 1034A Enlarge GCD
http://codeforces.com/problemset/problem/1034/A
题意问给定n个数，从中最少去掉多少个数之后可以使得剩下的数字的gcd严格大于原序列的gcd。
思路：先求出来原序列的gcd，无解的情况很容易判断，当序列中最大的数字就是gcd的时候无解。对于有解的情况，把每个数字除以这个gcd，剩下的一个序列就是gcd为1的序列，然后只要求出来去掉多少个数字之后可以使得序列gcd不为1就行了。这时候考虑去掉k个数字之后剩下的数字gcd为几，不妨设为w，很容易知道如果能求出来对于每个质数有多少个数字有这个质因子，那么取“在序列中出现最多次数的那个质数”的出现次数就是最大的剩下的序列中的元素个数，这里的出现次数是说如果ai%w==0则cnt++的意思。那么能求出来剩下的元素最多有多少个，也就能求出来去除的元素最少有多少个了。
比赛时候这个题是把我T爆了，主要是很难确定对于每个数暴力质因数分解好还是线性筛预处理出来1.5e7之内的素数比较好，一开始一直用的暴力质因数分解但是test23一直t，最后6min换了预处理素数ac了，其实手推渐进复杂度感觉二者差不多。。。。玄学卡常，而且最后过了也是800ms飘过。。。
[BIT][思维][反证][差分求极值] codeforces1030F Putting Boxes Together
题目：http://codeforces.com/problemset/problem/1030/F
这个题最主要的是自己没有想出来怎么求出那个“不动的点”，因为其实整体的cost用k去表示出来是很困难的，求出来也无法发现其极值点。但是如果考虑差分就会比较好做，很容易发现当当前设的k点变成k+1时，cost变化了(S(l,k)-S(k+1,r))*(p[k+1]-p[k])，其中S(l,r)=Σw[i](l<=i<=r)。这样的话很明显当且仅当S(l,k)≤S(k+1,r)S(l,k)≤S(k+1,r)时k+1比k更优。所以我们只要找到最小的k使得S(l,k)>=S(l,r)/2就行了！
然后是对于一个[l,r]对求出k之后，如何快速的求出其cost。
对于i∈(l,k)i∈(l,k) 代价是∑(pk−pi−(k−i))∗wi（l<=i<=k)
对于i∈(k,r)i∈(k,r) 代价是∑(pi−pl−(i−k))∗wi（k<=i<=r)
把pi-i看成一个整体，记为ai，就可以得到cost=∑(ak−ai)∗wi(l<=i<=k)+∑(ai−al)∗wi(k<=i<=r)
展开整理就可以得到cost=ak*(S(l,k)-S(k,r))-(Σwi*ai(l<=i<=k)-Σwi*ai(k<=i<=r))。这样的话用一个BIT快速求S(l,r)，另一个BIT快速求Σwi*ai就可以了。
wa点的话，发现了一个以前没有注意到的bug，那就是我每次判断都是if(x>mod)x%=mod;但是忽然意识到在有减法的运算中，还有一种下越界的可能性，所以应该是if(x>mod||x<-mod)x%=mod; 继续阅读“[BIT][思维][反证][差分求极值] codeforces1030F Putting Boxes Together”