这道题简化之后,
是要求出 一个整数n的所有最 为质数的因子(最简因子,不能再分),反正就拆成最小
比如
12
因子遍是 2 ,2, 3
用
int n;
for(int i=2;i*i<=n;i++){
while(n%i==0){
n/=i;
}
}
就能保证每次除的一定是质数因子
还有一个知识点就是
多重集合的排列数问题
例子:2 2 3 3 3 5
6个位置的,3种数,排列总数为 6!/(2!*3!)
记住即可
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<stack>
using namespace std;
typedef pair<int,int>PII;
const int N=(1<<20) +5;
#define endl '\n'
#define ll long long
int a[30];
int n,m;
ll get(int x){//计算阶乘
ll res=1;
for(int i=2;i<=x;i++){
res*=i;
}
return res;
}
void solve(){
while (cin>>n){
m=n;
memset(a,0,sizeof a);
int it=0;//a[it]里存放的是一种因子的个数
int num=0;//计数
for(int i=2;i*i<=m;i++){
if(m%i==0){
it++;
while (m%i==0){m/=i;a[it]++;num++;}
}
}
if(m>1){
a[++it]=1;
num++;
}
ll res=1;
for(int i=1;i<=it;i++){
res*= get(a[i]);
}
ll ans = get(num);
cout<<num<<" "<<ans/res<<endl;
}
}
void fast(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
}
int main(){
fast();
solve();
return 0;
}