问题 B: X-factor Chain

时间限制: 1 Sec  内存限制: 128 MB
提交: 15  解决: 6
[提交][状态][讨论版][命题人:150112200121][Edit] [TestData]

题目链接:http://acm.ocrosoft.com/problem.php?cid=1702&pid=1

题目描述

输入正整数 x,求 x 的大于 1 的因子组成的满足任意前一项都能整除后一项的序列的最大长度,以及满足最大长度的序列的个数。

输入

多组数据,每组数据一行,包含一个正整数 x

对于全部数据,1≤x≤220

输出

对于每组数据,输出序列的最大长度以及满足最大长度的序列的个数。

样例输入

2

3

4

10

100

样例输出

1 1

1 1

2 1

2 2

4 6

思路:讲该数质因数分解,可以得到序列最长即为总质因数的个数all,几条序列可有排列组合得知A(all,all)/[A(c1,c1)*A[c2,c2]*A[c3,c3]…],具体见代码。

 

代码:

#include<bits/stdc++.h>
using namespace std;
#define maxn 100000
#define ll long long
int m,p[maxn],c[maxn];
int all=0;
void divide(int n)//质因数分解,p数组存储因数的大小,c数组用来存储该质数的存在的个数 
{
	 m=0;
	 all=0;
	 for(int i=2;i*i<=n;i++)
	 {
	 	if(n%i==0)
	 	{
	 		p[++m]=i,c[m]=0;//i是质数 
	 		while(n%i==0)n/=i,c[m]++;//把n中所有的i都除掉 
		 }
	 }
	 if(n>1)
	 p[++m]=n,c[m]=1;
	 for(int i=1;i<=m;i++)
	 {
	 	all+=c[i];//看总质因数的个数(包括相同的) 
	 }
}
ll A(int x)//不是高精度,long long就行 
{
	ll sum=1; 
	for(int i=1;i<=x;i++)
	{
		sum*=i;
	}
	return sum;
}
int main()
{
	//ios::sync_with_stdio(flase);
	int n;
    while(cin>>n)
    {
    	if(n==1)cout<<"0 0"<<endl;//对1特判
    	else
    	{
    		memset(p,0,sizeof(p));
	    	memset(c,0,sizeof(c));
	    	divide(n);
	    	//cout<<A(all)<<endl;
	    	ll result=A(all);
	    	for(int i=1;i<=m;i++)
	    	{
	    		result/=A(c[i]);//排列组合 
			}
			cout<<all<<" "<<result<<endl;
		}
    	
	}
}