AcWing 1295. X的因子链
原题链接
中等
作者:
让我AC吧球球了
,
2022-02-28 20:21:10
,
所有人可见
,
阅读 199
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N = (1 << 20) + 10;
typedef long long LL;
int cnt;
int primes[N],minp[N];
bool st[N];
void funct(int n){
for(int i = 2;i<=n;i++){
if(st[i] == 0){
minp[i] = i;
primes[cnt++] = i;
}
for(int j = 0;primes[j] * i<n;j++){
st[primes[j]*i] = true;
minp[primes[j]*i] = primes[j];
if(i%primes[j] == 0) break;
}
}
}
int main(){
int x;
funct(N-1);
int fun[N],sum[N];
while(scanf("%d",&x) != -1){
int k = 0 ;
int tot = 0;
while(x>1){
int p = minp[x];
fun[k] = p, sum[k] = 0;
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;i++){
for(int j = 1; j <= sum[i];j++){
res /=j;
}
}
printf("%d %lld\n",tot,res);
}
return 0;
}