B.Quadratic equation（二次剩余）
•先行知识
二次剩余
[1]
[2]
•思路
知道 $x+y$ 和 $ x \times y $
那计算x,y 自然是$ ( x-y )^{^{2}} = ( x+y )^{^{2}} - 4xy = b^{2}-4c $
设$b^{2}-4c = d$,利用二次剩余求解
\begin{cases}
1,&d^{\frac{p-1}{2}}\text{在模$p$意义下是二次剩余}\\
-1,&d^{\frac{p-1}{2}}\text{在模$p$意义下是非二次剩余}\\
0,&d^{\frac{p-1}{2}}\equiv0\pmod p
\end{cases}有解时：
①当 $d=0$ 时，两个解相等，都为$\frac{b}{2}$
②当d是 $mod \ p$ 的平方剩余时有$d^{\frac{p-1}{2}} \equiv 1 (mod \ p)$
设$p-1=2^{t}\times s,(2∤s)$,显然$t=1$
所以$ ( x-y )=d^{\frac{s+1}{2}}$是$( x-y )$的一个解
所以$x-y=d^{\frac{s+1}{2}}= d^{\frac{p+1}{4}}$
由于$p=1000000007$,所以$ (p+1) \ mod \ 4 =0$可行
因为$x-y= d^{\frac{p+1}{4}}$，所以$(x - y)\mod \ p \equiv d^{\frac{p+1}{4}} \ mod \ p$ 设为 a
然后再利用 $x + y \equiv b(mod \ p)$
$\left \{ _{x + y \equiv b(mod \ p)}^{x - y \equiv b(mod \ p)} \right.$
得到x,y
注意 此时是在模p的情况下，
在除以2的时候记得除法取模
$\frac{m}{n} \ mod \ p = mn^{p-2} \ mod \ p$
•代码
D.Knapsack Cryptosystem（折半枚举）
•题意
给出一个长度为n的集合a,
从中选任意个数，使得这些数的和为s
•思路
由于长度最大为36,一共有$2^{36}$种情况
挨个枚举肯定会TLE
利用折半枚举，两个$2^{18}$
•代码
E.All men are brothers（并查集+思维）
•题意
一开始有n个人不认识。有m个回合，他们中的两个轮流交朋友。
朋友关系是相互的、可传递的。
如果A是B的朋友，那么B也是A的朋友。
例如，如果A是B的朋友，B是C的朋友，那么A和C是朋友。
在开始和每个回合之后，请计算从中选择四个人的方法的数量，这样这四个人中的任何两个都不是朋友。
•思路
假设现在有5个朋友圈A,B,C,D,E
5个朋友圈里的人数分别为a,b,c,d,e
那么现在的方式有$(abcd+abce+abde+acbd+acde)$种
此时令A B做朋友，也就是A B朋友圈合并
那现在的方式有$((a+b)cde)$,也就是$(acde+bcde)$种
减少了$(abcd+abce+abde)$,即$ab(cd+ce+de)$种
因为$cd+ce+de=((c+d+e)^{2}-(c^{2}+d^{2}+e^{2}))/2$
我们可以利用并查集合并、查找集合，
用一个s记录所有集合的平和方
由于每次时两个集合合并，a,b不合并的平方和为$a^{2}+b^{2}$
合并后的平方和为$(a+b)^{2}=a^{2}+b^{2}+2ab$
所以每次合并后$s+=2ab$
注意 当所有集合都不合并时答案$\textrm{C}_{n}^{4}$可能会long long溢出，
所以使用unsigned long long
•代码