pe-0926

首先对阶乘分解质因数,落到1e7内的所有质数上.
然后对于一个阶,发现是对所有质数取min(就是说,假如质数为2和5,次方分别为2和1,在取20的时候,0会取各个质数的min,也就是得到min(2,1)=1)
这启示我们用容斥定理,对每个min的结果,显然是小于2的次方数(实测1e7!中2的次方大概就是1e7),枚举min.
对于min,卡出来每个次方的下界(不能低于这个),可以不派出这个因子.但是派出就不能低于枚举的min,最后减掉2的次方数(都不派出),得到 $O(\frac{n}{\log n}\log((10^7)!))$ 大概是1e12的数量级,核心代码

for(int i=1;i<=po[1];++i){
	dp[i]=1;
	for(int j=1;j<=ptop;++j){
		dp[i]=dp[i]*(1+po[j]/i)%mod;
	}
}

但是我们发现这个 po[j]/i 是可以分块的,所以对每个质数考虑合并贡献,用区间乘线段树维护,复杂度 $O(\frac n{\log n}\sqrt n\log n)=O(n^{3/2})$ (前边是质数个数,中间是数论分块,后面是线段树操作的复杂度),笔者跑了2s多过了.

这个题的thread乱杀,有 $O(n^{3/4})$ 过的,还有 $O(n\log\log n)$ 过的,总之做法很多,强烈推荐一看,拓展思路.