AcWing
1295. X的因子链
前置知识点：
算术基本定理：因式分解的定理，所有的整数都可以唯一分解成若干个质因子乘积的形式，$N=P_1^{\alpha _1}\times P_2^{\alpha _2}\times \cdots \times P_k^{\alpha _k}$，其中$P_i$是素数，每一个$\alpha _i \ge 0$.
线性筛法（欧拉筛法），在$O(n)$的时间复杂度内，求出来$1\sim n$中所有的质数，以及每一个数的最小质因子。
线性筛素数板子：
int primes[N], cnt; // 素数、素数的个数
bool st[N]; // 每个数是否被筛过
int minp[N]; // 每个数的最小质因数，可选
void getprime(int n){ // 线性筛素数
for(int i = 2; i <= n; i ++){
if(!st[i]){ // 质数
primes[cnt ++] = i;
minp[i] = i; // 可选
}
for(int j = 0; primes[j] * i <= n; j ++){ // 合数
int t = primes[j] * i;
st[t] = true;
minp[t] = primes[j]; // 可选
if(i % primes[j] == 0) break;
}
}
}
将题目中所给出的数拆分成若干个质因子的乘积形式，只需要循环除以当前数字的最小质因子，直到当前数字为$1$. 那么序列的长度即为所有质因子的总个数，种类数即为这些质因子的排列。但是，质因子之间存在相等的情况。例如，$540=2^2\times 3^3\times 5^1$，其$6$个质因子$2, 2, 3, 3, 3, 5$的排列数并不是$6!$，而是$\frac{6!}{2!\cdot 3!}$，因为两个$2$的排列方式和三个$3$的排列方式不应考虑进总的方案数量。
代码：
#include <bits/stdc++.h>
using namespace std;
const int N = (1 << 20) + 10;
int primes[N], cnt;
bool st[N];
int fact[30], k; // 每种质因子的数值，质因子的种数
int sum[30]; // 每种质因子的个数
int minp[N]; // 每个数的最小质因数
typedef long long LL;
void getprime(int n){ // 线性筛素数
for(int i = 2; i <= n; i ++){
if(!st[i]){ // 质数
primes[cnt ++] = i;
minp[i] = i;
}
for(int j = 0; primes[j] * i <= n; j ++){ // 合数
int t = primes[j] * i;
st[t] = true;
minp[t] = primes[j];
if(i % primes[j] == 0) break;
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
getprime(N - 1);
int x;
while(cin >> x){
k = 0; // 每轮重置
int tot = 0; // 质因数的总个数
while(x > 1){
int p = minp[x];
fact[k] = p, sum[k] = 0; // 重置sum
while(x % p == 0){
x /= p;
sum[k] ++;
tot ++;
}
k ++;
}
LL res = 1;
for(int i = 1; i <= tot; i ++) res *= i;
for(int i = 0; i <= k - 1; i ++)
for(int j = 1; j <= sum[i]; j ++)
res /= j;
cout << tot << ' ' << res << '\n';
}
return 0;
}