X的因子链+素数线性筛法
作者:
NAGIoto
,
2024-04-09 23:46:53
,
所有人可见
,
阅读 3
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = (1 << 20) + 10;
int primes[N] , cnt; // 存所有素数
bool st[N]; //存有没有被筛过
int min_primes[N]; //存第i个位置的最小质因子
void get_primes(int n){ //质数线性筛法
for(int i=2; i<=n; i++){
if(!st[i]){
min_primes[i] = i; //(本题追加) i是质数 所有第i个位置的质因子素是它本身
primes[cnt ++] = i;
}
for(int j=0; primes[j] * i <= n; j++){
int temp = primes[j] * i;
st[temp] = true; //将合数筛掉,使用的是最小质因子
min_primes[temp] = primes[j]; //here has some
if(i % primes[j] == 0) break; // primes[j]一定小于等于i的质因子
}
}
}
int main(){
get_primes(N - 1);
int x;
int fact[22]; //因子个数
int sum[N]; //每个因子出现的次数
int totl; //总共的因子出现的次数
LL res;
while(cin >> x){
int k=0; //第k个因子
totl = 0; //初始化
while(x > 1){
int p = min_primes[x]; //最小质因子
fact[k] = p; //记录当前质因子 ,本题没用
sum[k] = 0;
while(x % p == 0){
sum[k] ++ ;
totl ++;
x /= p;
}
k ++;
}
res = 1;
for(int i=1; i<=totl; i++) res *= i;
for(int i=0; i<k; i++)
for(int j=1; j<=sum[i]; j++){
res /= j;
//cout << res << " ";
}
// cout << endl;
cout << totl << " " << res << endl;
}
return 0;
}