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

思路

一种简单的构造方法就是将作为最后一个数,之前每个数是后一个数除以任意一个因子,这样构造一定是最优的.
因此第一个答案就显而易见了,就是的质因子个数.(这里若,算个质因子)
如果不是任何质数的平方的倍数,那么方案就是每次除以的因子的全排列.如果,的排列会有重复,也就是说会重复计算.因此若,第二个答案就是.
很简单吧.复杂度是.

代码

#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;
}