AcWing 1295. X的因子链(详细注释版)
原题链接
中等
作者:
手法的小曲
,
2024-04-03 21:17:44
,
所有人可见
,
阅读 2
y总题解详细注释版 – 举例说明
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = (1 << 20) + 10;
int primes[N], cnt;
int minp[N];
bool st[N];
void get_primes(int n) // O(n)
{
for(int i = 2; i <= n; i++){
if(!st[i]){
minp[i] = i;
primes[cnt++] = i;
}
// 从小到大枚举所有的质数,把质数的i倍筛掉
for(int j = 0; primes[j] * i <= n; j++){
st[primes[j] * i] = true;
minp[primes[j] * i] = primes[j];
//p[j]一定不大于i的最小质因子
if(i % primes[j] == 0) break;
}
}
}
int main()
{
get_primes(N - 1);
int fact[30]; // 存取每个质因子,如100 = (2^2) * (5^5),fact[0]=2,fact[1]=5
int sum[N]; // 存取每个质因子对应的个数 sum[0] = 2, sum[1] = 2;
int x;
while(scanf("%d", &x) != -1){
int k = 0; // 质因子种类,100有两种质因子,则k取 0和1
int total = 0; // 质因子的总数量,100有2个2、2个5,则总数为4
while(x > 1){
int p = minp[x]; // 取出x的最小质因子
fact[k] = p, sum[k] = 0;
while(x % p == 0){
x /= p;
sum[k]++; // 每个质因子对应的个数
total++;
}
k++;
}
LL res = 1;
// 求total的阶乘
for(int i = 1; i <= total; i++) res *= i;
// 求每个质因子个数的阶乘
for(int i = 0; i < k; i++){
for(int j = 1; j <= sum[i]; j++){
res /= j;
}
}
printf("%d %lld\n", total, res);
}
return 0;
}