堆叠 解题报告 堆叠
题意：
给出一堆质数，求这些质数乘起来的数的约数之积mod1e9+7
数据范围：
质数个数小于等于2e5，质数大小小于2e5
设
[N=prod_{i=1}^k p_i^{c_i}
]
[C=prod_{i=1}^k c_i+1
]
则答案为
[prod_{i=1}^k p_i^{frac{C}{c_i+1} imes sum_{i=1}^{c_i}i } mod p
]
先求指数
要用到扩展欧拉定理
即
[a^k equiv a^{k \% varphi (p)} (mod p)$$,$p$质
注意到我们要把1e9+6拆成$2,500000003$再用CRT合并
注意在求逆元的时候要先把$2$或$5000000003$的项给拿出来，求完了再扔回去
事实上可以做到更简单
把答案化简为
$$prod_{i=1}^k p_i^{frac{C imes c_i}{2}} mod p]
我们在求出(C)的时候随便找一个偶数把(2)给拿掉，如果没有那么(c_i)一定是偶数，反正找一个把2除了就行啦
代码只写了个假的CRT的版本，就不放出来了
2018.9.2