BZOJ3114 - Click Here
Description
给定一个数N，求所有满足最小公倍数为N的a,b的和对1000000007取模。
例如当N=6时，有如下对数(1,6),(2,6),(2,3),(3,6),(6,6),其和为=(1+6)+(2+6)+(2+3)+(3+6)+(6+6)=7+8+5+9+12=41。
现在给你N的分解质因数式，请你求出相应的值。
Input
多组测试数据。第一行T表示数据组数。
每组数据第一行为M，表示有M的质因子。
下面M行，每行两个数，第一行为这个质因子，第二行为这个质因子在N中出现的次数。
100%保证T<=500，M<=15,每个质因数是2-1000内的质数,次数大于等于1小于等于50
Output
T行，每行一个整数表示f(N)的值。因为答案可能很大，所以只需输出答案 mod 1000000007。
Solutions
MDZZ居然随机到一道结论题。
题目求$\sum(a+b), \, lcm(a,b)=N$，由于$lcm(a,b)=\frac{ab}{gcd(a,b)}$，因此很容易想到用$gcd(a,b)$表示$a,b$。
即设$d=gcd(a,b)$，则$a=dx,b=dy$，且$gcd(x,y)=1$。
此时，$lcm(a,b)=N \iff dxy=N$，所求答案为$\sum d(x+y), \, dxy=N$。
现在，思考一下$xy$需要满足什么性质。
由上面结论得$xy=\frac{N}{d}$，由唯一分解定理得$N=p_1^{k_1} \cdot p_2^{k_2} \cdot p_3^{k_3}…$。
因为$xy$为整数，因此$d=p_1^{k’_1} \cdot p_2^{k’_2} \cdot p_3^{k’_3}…$且$0 \leq k’_i \leq k_i$。
此时，等式为$\frac{N}{d}=p_1^{k_1-k’_1} \cdot p_2^{k_2-k’_2} \cdot p_3^{k_3-k’_3}…$，该式等于两个互质的数$xy$相乘。
因此$x$和$y$其实就是将$\frac{N}{d}$拆分成了两部分，每部分都由不同的质数组成。
现在要求的$\sum(x+y)$，也就是求$\frac{N}{d}$拆分成所有合法数字之和。
这个答案为$(1+p_1^{k_1-k’_1})(1+p_2^{k_2-k’_2})(1+p_3^{k_3-k’_3})…$。数学归纳法可证，此处不写出。
将上诉答案用$f(\frac{N}{d})$表示，那么现在所求的答案为$\sum d \cdot f(\frac{N}{d})$。
然后就可以枚举$d$，求出答案了。可是$d$的组合特别多，还是会T，因此需要再合并一次。
利用类似的思想，设$d=p_1$，$d=p_1^2$，$d=p_1^3$……
最后会得到$\sum d \cdot f(\frac{N}{d})=n+\prod(k_ip_i^{k_i}+\sum_{j=0}^{k_i}p_i^j)$。
时间复杂度$O(T\sum k_i)$
CODE
CODE - Click Here