X-factor Chain

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1056 字

给定x，求其大于1的因子组成的整除链x0|x

一本通
练习

正文

/*
原题：T1628「一本通 6.3 练习 1」X-factor Chain
题意：给定 x，求其大于 1 的因子组成的整除链 x0|x1|...|xm=x 的最大长度，以及达到该长度的链个数。
思路：对 x 质因数分解得指数 e1..ek；最大长度 = Σei，链个数 = (Σei)! / Π(ei!)（多重组合数）。
复杂度：时间 O(x log log x + 数据量) / 空间 O(x)
易错点：x=1 时长度为 0、个数为 1；阶乘最大为 20!，long long 可装下。
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX=(1<<20); // 2^20 = 1048576
int spf[MAX+1];
ll fact[21];
void sieve(){
    for(int i=2;i<=MAX;i++){
        if(!spf[i]){
            for(int j=i;j<=MAX;j+=i){
                if(!spf[j]) spf[j]=i;
            }
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    sieve();
    fact[0]=1;
    for(int i=1;i<=20;i++) fact[i]=fact[i-1]*i;
    ll x;
    while(cin>>x){
        ll sum=0, den=1;
        ll t=x;
        while(t>1){
            int p=spf[t], e=0;
            while(t%p==0){
                t/=p;
                e++;
            }
            sum+=e;
            den*=fact[e];
        }
        ll cnt=(sum==0)?1:fact[sum]/den;
        cout<<sum<<" "<<cnt<<"\n";
    }
    return 0;
}

X-factor Chain

正文

一本通·提高篇的其它内容