算术基本定理：
#include <iostream> #include <algorithm> using namespace std; const int N=(1<<20)+10; int primes[N],cnt; bool st[N]; int minp[N]; typedef long long LL; void get_primes(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++) { minp[primes[j]*i]=primes[j]; st[primes[j]*i]=true; if(i%primes[j]==0) break; } } } int main() { get_primes(N-1); int x; int sum[N],fact[30]; while(cin>>x) { int tot=0, k=0; while(x>1) { int p=minp[x]; fact[k]=p,sum[k]=0; while(x%p==0) { sum[k]++; tot++; x/=p; } 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; cout<<tot<<' '<<res<<endl; } return 0; }
