A.[AHOI2007]密码箱
Description
在一次偶然的情况下，小可可得到了一个密码箱，听说里面藏着一份古代流传下来的藏宝图，只要能破解密码就能打开箱子，而箱子背面刻着的古代图标，就是对密码的提示。经过艰苦的破译，小可可发现，这些图标表示一个数以及这个数 与密码的关系。假设这个数是n，密码为x，那么可以得到如下表述:密码x大于等于0，且小于n，而x的平方除以n，得到的余数为1。 小可可知道满足上述条件的x可能不止一个，所以一定要把所有满足条件的x计算出来，密码肯定就在其中。计算的过程是很艰苦的，你能否编写一个程序来帮助小可可呢？（题中ｘ， ｎ均为正整数）
Input
输入文件只有一行，且只有一个数字 (n(1leq nleq 2 imes 10^9))
Output
你的程序需要找到所有满足前面所描述条件的x，如果不存在这样的x，你的程序只需输出一行“None”(引号不输出)，否则请按照从小到大的顺序输出这些x，每行一个数。
思路
显然想让我们求的是这个式子：
稍加思索，可以得到这个形式：
设 (n=a*b) ，
则 (a*b|(x+1)(x-1)) ，即 (a|x+1,b|x-1) 或 (a|x-1,b|x+1) 。
设 (a<b) ，枚举 (a) ，然后枚举 (x=kb+1) 或 (x=kb-1) ，(a) 枚举到 (sqrt n) 即可
时间复杂度 (O(sqrt n*sqrt n)=O(n))
B.[AHOI2005]约数研究
此题水炸了，不想写（尤其是考试的时候，脑子也不知道在想什么，最后才看出来）
思路
我看到这题的第一想法：用 (f(n)=(p_1+1)(p_2+1)...(p_k+1)) 求出每个数，然后觉得 (n) 有点大，就放弃了
考虑每个因子在式子中的贡献，可知2这个因子出现了 (lfloorfrac n2 floor) 次，3这个因子出现了 (lfloorfrac n3 floor) 次，以此类推，可知 (p_i) 的贡献是 (lfloorfrac n{p_i} floor) ，则答案为 (lfloorfrac n2 floor+lfloorfrac n3 floor+...+lfloorfrac n{p_i} floor+...) 。
可以选择把 N 以下的 (lfloorfrac n{p_i} floor) 预处理出来
C.BZOJ2142 礼物
Description
一年一度的圣诞节快要来到了。每年的圣诞节小E都会收到许多礼物，当然他也会送出许多礼物。不同的人物在小E心目中的重要性不同，在小E心中分量越重的人，收到的礼物会越多。小E从商店中购买了n件礼物，打算送给m个人，其中送给第i个人礼物数量为wi。请你帮忙计算出送礼物的方案数（两个方案被认为是不同的，当且仅当存在某个人在这两种方案中收到的礼物不同）。由于方案数可能会很大，你只需要输出模P后的结果。
Input
输入的第一行包含一个正整数P，表示模；第二行包含两个整整数n和m，分别表示小E从商店购买的礼物数和接受礼物的人数；以下m行每行仅包含一个正整数wi，表示小E要送给第i个人的礼物数量。
Output
若不存在可行方案，则输出“Impossible”，否则输出一个整数，表示模P后的方案数。
HINT
设 (p=p_1^{c_1}*p_2^{c_2}*p_3^{c_3}*...*p_t^{c_t})，(p_i) 为质数。
对于100%的数据，(1leq nleq 10^9,1leq mleq 5,1leq p_i^{c_i}leq 10^5)。
思路
(exLucas)：干 他 就 完 了
按照正常的思路，可列出组合数相乘的式子：
但是我们知道，这样暴力算肯定是不行（可行的，并且是正解(╯▔皿▔)╯，下面不想看的就不看了）的，所以将 (C_n^m) 展开，即：
不难发现，原式中的前一项的分母和后一项的分子是可以相消的。可将原式化简为：
然后预处理出阶乘的逆元，但是因为友(e)善(du)的出题人明确说明 (p) 不一定是质数，所以求逆元需要分开，亿点点求，即求出每个 (n!\%p_k^{c_k})
（下面是我之前的总结）
-
如何求 (n!\%p_i^{k_i})
我们以 (n=19,p_i=3,k_i=2) 为例
(n!=1∗2∗3∗4∗5∗6∗7∗8∗9∗10∗11∗12∗13∗14∗15∗16∗17∗18∗19\=(1∗2∗4∗5∗7∗8∗10∗11∗13∗14∗16∗17∗19)∗36∗(1∗2∗3∗4∗5∗6))
根据这个例子发现，求解n!可以分为3部分：第一部分是 (p_i)的幂的部分，也就是 (3^6)即 (p_i^{lfloorfrac n{p_i} floor})，可以直接求解；第二部分是一个新的阶乘，也就是6!即 (lfloorfrac n{p_i} floor!)，可以递归下去求解；第三部分是除前两部分之外剩下的数
-
考虑第三部分如何求解
发现第三部分在模 (p_i^{k_i}) 意义下是以 (p_i^{k_i}) 为周期的，即:
((1∗2∗4∗5∗7∗8)≡(10∗11∗13∗14∗16∗17)~(mod~p_i^{k_i})) ，所以只要求出 (p_i^{k_i}) 的长度即可；
但是还剩下一个孤立的19，可以发现剩下孤立的数长度不会超过 (p_i^{k_i}) ，只需要暴力求解即可
-
最后一个问题是对于求出的 (m!\%p_i^{k_i}) 和 ((n-m)!\%p_i^{k_i}) 有可能与 (p_i^{k_i}) 不互质，无法求逆元
所以要将 ((n-m)!\%p_i^{k_i}) 和 (m!\%p_i^{k_i}) 中质因子 (p_i) 先全部除去，求出逆元后再全部乘回去
计算n!中质因子p的个数x的公式为 (x=lfloorfrac np floor+lfloorfrac n{p^2} floor+lfloorfrac n{p^3} floor+...)
递推式也可以写为 (f(n)=f(lfloorfrac np floor)+lfloorfrac np floor)
(Update:2020.7.25.10:06~~:) 因为 (mleq 5) 所以直接暴力好像更快（
(Update:2020.7.25.9:12) ：果然，正解是直接 (ex~Lucas) 定理 ヽ(*。>Д<)o
（特判：当 (sumlimits_{i=1}^mw_i>n) 时，无解）
D.P3166 [CQOI2014]数三角形
思路
三角形数量=在平面上随便找仨点-三点共线情况
在平面上随便找仨点 (=C_{(n+1)(m+1)}^3)
三点共线有三种情况：横着，竖着，斜着
横着，竖着 (=(n+1)C_{m+1}^3+(m+1)C_{n+1}^3)
主要是斜着的比较难搞，有斜率上升和下降两种。不难发现两种数量相等，所以我们设 (ans) 为上升的数量，最后乘二即可
设 (AB) 为长度为 (i) 的竖着的一条线段， (BC) 为长度为 (j) 的横着的一条线段
画图可以看出，(AC) 上的点数为 (gcd(i,j)+1) （不加顶点为 (gcd(i,j)-1) ）
则像 (A,B) 这样横坐标差 (j) ，纵坐标差 (i) 的点对共有 ((n-i+1)(m-j+1))
枚举 (i,j) 可得
此时直接枚举是 (O(nm)=O(n^2)) ，考虑 (gcd) 的计算的话可能会达到 (O(n^2log n)) 。
优化复杂度
通过欧拉反演可以将 ([gcd(i,j)=1]) 化为 (sum_{d|gcd(i,j)}varphi(d)) 。（原理：(sum_{d|n}varphi(d)=n) 下面证明）
则，原式转化为：
因为 (varphi(1)=1) ，所以可以微微转化一下：
接下来，我们看看 (d|gcd(i,j)) 的含义：
(i,j) 的最大公因子的每个因子 。
也就是 (i,j) 的每个公约数
枚举 (i,j) 再枚举他们的所有公约数，等价于枚举每个约数 (d) 再枚举 (d) 的 (i) 倍、(j) 倍。
那 (d) 的取值范围可化为 ([2,min(n,m)]) ， (i,j) 最小取 (1) ，最大取 (lfloorfrac dn floor,lfloorfrac dm floor) ，即：
很明显(这我开始也不明显)，(sumlimits_{i=1}^{lfloor n/d floor}(n-id+1)) 是等差数列求和，
首项为 (n-d+1) ，末项是 (n-lfloor dfrac nd floor d+1) 即 (n~mod~d+1) ，项数是 (lfloor dfrac nd floor) ，由通项公式得：
同理有：
最后得到：
欧拉函数用欧拉筛线性预处理出来，枚举 (d) 复杂度 (O(min(n,m))=O(n))
(sum_{d|n}varphi(d)=n) 证明（会的可以跳过）
我们首先看这么几个数
如果要化成 (frac ab) 这样的最简分数的形式，要满足两个条件：
(
1.b|n~~
2.gcd(a,b)=1
)
，显然对于每个 (b)，共有 (varphi(b)) 个，而 (n) 的约数共有 (sum_{d|n}) 个，那么可得：
那个的严格证明我忘了，嘻嘻嘻
下面的题有了
E.BZOJ4173 数学
题目
懒得放了。。。。
思路
通过题目，我们可以设 (m=q_1*k+r_1,n=q_2*k+r_2) ，则题目中的式子可化为 (r_1+r_2geq k) ，所以 (lfloordfrac{m+n}k floor=q_1+q_2+1) ，则 (dfrac{m+n}k-dfrac nk-dfrac mk=1)
那么 (sum_{kin S(n,m)}varphi(k)) 可化为 (sumlimits_{k=1}^{m+n}varphi(k)[frac{m+n}k-frac nk-frac mk=1])，即：
我们设 (F(n)=sumlimits_{k=1}^{n}varphi(k)lfloorfrac{n}k floor)
则可化为 (F(n+m)-F(n)-F(m)) ，单独考虑 (F(n)) ：
通过 (sum_{d|n}varphi(d)=n) ，可将 (F(n)) 转化为：
所以，上式化为：
这显然等差数列求和，于是：
所以，(varphi(m)*varphi(n)*sum_{kin S(n,m)}varphi(k)) 就等于：
然后用欧拉筛或者别的办法求 (varphi) 即可
因为直接求 (varphi) 时间复杂度是 (O(sqrt n)) 的，所以总时间复杂度为 (O(n))
(sum_{d|n}varphi(d)=n) 的小证明
设 (n=prodlimits_{i=1}^mp_i^{a_i}) ，
由于欧拉函数是积性函数，则有：
因式分解，上式等价于：
（有的是放了题，有的只写了思路，(●'◡'●)）