1454-D, *1300

Problem - 1454D - Codeforces

문제

• $n(2\leq n \leq 10^{10})$이 주어질 때 다음을 만족하는 수열 $a_{1},\ a_{2},\ ...,\ a_{k}$의 최대 길이를 구하라
• $a_{1} \cdot a_{2} \cdot \cdot \cdot a_{k} = n$
• $a_{i}\mid a_{i+1},\ i=1,\ 2,\ ...,\ k-1$

 

$O(\sqrt n)$

$n=2^{e_{0}}p_{1}^{e_{1}}p_{2}^{e_{2}}\cdot \cdot \cdot p_{t}^{e_{t}}$
$n$의 표준분해가 위와 같다고 할 때, 수열 {a}의 최대길이는
$$\mathrm{max(e_{0},\ e_{1},\ ...,\ e_{t})}$$

#include <bits/stdc++.h>
#define endl "\n"
#define loop(i, n) for(int i = 1; i <= n; i++)
using namespace std;
typedef long long ll;
 
ll n;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int t;
    cin >> t;
    while(t--){
        cin >> n;
        vector<pair<int, ll> > v;
 
        if(n % 2 == 0){
            int cnt = 0;
            while(n % 2 == 0){
                cnt++;
                n >>= 1;
            }
            v.push_back({cnt, 2});
        }
        for(ll fac = 3; fac*fac <= n; fac += 2){
            if(n % fac == 0){
                int cnt = 0;
                while(n % fac == 0){
                    cnt++;
                    n /= fac;
                }
                v.push_back({cnt, fac});
            }
        }
        if(n > 1) v.push_back({1, n});
 
        sort(v.rbegin(), v.rend());
 
        vector<ll> ans(v[0].first, v[0].second);
        for(ll i = 1; i < v.size(); i++){
            for(ll j = 0; j < v[i].first; j++) ans[ans.size()-1] *= v[i].second;
        }
 
        cout << ans.size() << endl;
        for(auto e: ans) cout << e << ' ';
        cout << endl;
 
    }
 
    return 0;
}cs