bzoj2186

1 ~ N!M! 互质的数的个数,M <= N

即求$\frac{n!}{m!}\phi(m!)$
其中$\phi(m!) = m!(p_1 - 1)(p_2 -1)…(p_k - 1)/p_1p_2…p_k$
因此我们预处理出质因子和逆元,递推求$\phi(m!)/m!$

poj1845

求$a^b$的因子和

即求 $sum_n=\prod_1^k \sum_0^{e_i+b}p_i^j$
等比数列求和可以用二分求和
如果直接用公式,注意若gcd(p_i-1,mod) == 1,需要特判
此时恰好 p_i%mod = 1,所以和为 $e_i+b+1$