给定一个数X.

1=X0, X1, X2.....Xm = X 是X的因数

求一串因数,要求Xi | Xi+1,即上一个因数能整除下一个因数,

问这条串就的最长长度,和有多少条这样长度的串.

X = p1^a1 * p2^a2 ... pn^an

Xi = p1^b2 * p2^b2 ...pk^bk... pn^bn,

Xi+1 = p1^b2 * p2^b2 ...pk^(bk+1)... pn^bn,

 

要使length最长,只要从1开始，每次只乘以X的一个质因数即可,即length = (a1+a2+...an)

而方法数就是X的质因数的重排列数,way = (a1+a2+...an)!/(a1!a2!...an!)

/*  * poj3421.c  *  *  Created on: 2011-10-10  *      Author: bjfuwangzhu */ #include
     
       #include
      
        #include
       
         #define LL long long #define nmax 1500 int prime[nmax], num[nmax]; int plen, nlen; void mkprime() {
   int i, j;     memset(prime, -1, sizeof(prime)); for (i = 2; i < nmax; i++) {
   if (prime[i]) {
   for (j = i + i; j < nmax; j += i) {
                   prime[j] = 0;             }         }     } for (i = 2, plen = 0; i < nmax; i++) {
   if (prime[i]) {
               prime[plen++] = i;         }     } } void solve(int n) {
   int i, j, te, cnt, res1;     LL res2;     te = (int) sqrt(n * 1.0); for (i = 0, nlen = 0; (i < plen) && (prime[i] <= te); i++) {
   if (n % prime[i] == 0) {
               cnt = 0; while (n % prime[i] == 0) {
                   n /= prime[i];                 cnt++;             }             num[nlen++] = cnt;         }     } if (n > 1) {
           num[nlen++] = 1;     } for (i = 0, res1 = 0; i < nlen; i++) {
           res1 += num[i];     } for (i = 2, res2 = 1; i <= res1; i++) {
           res2 = res2 * i;     } for (i = 0; i < nlen; i++) {
   for (j = 2; j <= num[i]; j++) {
               res2 = res2 / j;         }     }     printf("%d %lld\n", res1, res2); } int main() {
   #ifndef ONLINE_JUDGE     freopen("data.in", "r", stdin); #endif int n;     mkprime(); while (~scanf("%d", &n)) {
           solve(n);     } return 0; }