给出(n(1e6))，请问(n!)的 因子的因子的个数。
因子的个数求解不难，可以知道是质因数分解。
对于一个质因数(P_i^{k})，可以知道其因子的数量的是((k + 1))。对于具体的(p_i^0)，有一个因子1；对于(p_i^1)，有两个因子1, (p_1)；依次类推。易得公式为：
[res=\prod{(k+1)*(k+2)/2} ]
其中k是各个质因子的幂次
由于N的范围是(1e6)，我们用(N\sqrt{N})直接分解显然是会超时的。我们可以用筛法优化质因数的分解，达到O(n)的时间复杂度。
#include
using namespace std;
typedef long long ll;
const ll mod = 1e7 + 7;
const int N = 1000005;
vector primes;
bool vis[N];
int n;
void init()
{
for(int i = 2; i n)
break;
ll tmp = calc(x);
res = (res * ((tmp + 1) * (tmp + 2)) / 2ll) % mod;
}
printf("%lld\n", res);
}
}
Original: https://www.cnblogs.com/DM11/p/16701332.html
Author: DM11
Title: C. Divisors of the Divisors of An Integer（质因数分解，数论） 2018-2019 ACM-ICPC, Asia Dhaka Regional Contest
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/604261/
转载文章受原作者版权保护。转载请注明原作者出处！