题解 | 信息学奥赛一本通 X-factor Chain

思路

一种简单的构造方法就是将 $N$ 作为最后一个数,之前每个数是后一个数除以任意一个因子,这样构造一定是最优的.
因此第一个答案就显而易见了,就是 $N$ 的质因子个数 $c$ .(这里若 $p_i^{c_i}|N$ , $p_i$ 算 $c_i$ 个质因子)
如果 $N$ 不是任何质数的平方的倍数,那么方案就是每次除以的因子的全排列 $c!$ .如果 $p_i^2|N$ , $p_i$ 的排列会有重复,也就是说 $...,p_i,...,p_i,...$ 会重复计算.因此若 $N=\prod_{i}p_i^{c_i}$ ,第二个答案就是 $\frac{(\sum c_i)!}{\prod c_i!}$ .
~~很简单吧~~.复杂度是 $O(T\sqrt N)$ .

代码

#include<bits/stdc++.h>
using namespace std;
#define i64 long long
#define fp( i, b, e ) for ( int i(b), I(e); i <= I; ++i )
#define fd( i, b, e ) for ( int i(b), I(e); i >= I; --i )
#define go( i, b ) for ( int i(b), v(to[i]); i; v = to[i = nxt[i]] )
template<typename T> inline void cmax( T &x, T y ){ x < y ? x = y : x; }
template<typename T> inline void cmin( T &x, T y ){ y < x ? x = y : x; }

clock_t t_bg, t_ed;
int N, c1, c2;
i64 ans1, ans2;

signed main(){
    t_bg = clock();
    while( ~scanf( "%d", &N ) ){
        ans1 = ans2 = 1, c1 = 0;
        for ( int i = 2; i * i <= N; ++i ){
            c2 = 0;
            while( N % i == 0 ) ans1 *= ++c1, ans2 *= ++c2, N /= i;
        } if ( N > 1 ) ans1 *= ++c1;
        printf( "%d %lld\n", c1, ans1 / ans2 );
    }
    t_ed = clock();
    fprintf( stderr, "\n========info========\ntime : %.3f\n====================\n", (double)( t_ed - t_bg ) / CLOCKS_PER_SEC );
    return 0;
}