Lời giải.

Gọi ~n = p_1^{a_1}p_2^{a_2}\cdots p_m^{a_m}~. Mỗi ước ~d~ của ~n~ có thể được biểu diễn bằng một vector ~(e_1,e_2,\ldots,e_m)~, trong đó ~0 \le e_i \le a_i~ và ~d = p_1^{e_1}p_2^{e_2}\cdots p_m^{e_m}~.

Với hai ước ~x~ và ~y~, ta có ~x \mid y~ khi và chỉ khi mọi tọa độ trong vector của ~x~ đều không lớn hơn tọa độ tương ứng trong vector của ~y~.

Vì vậy, bài toán tương đương với việc chia tất cả các điểm trong một hình hộp nhiều chiều thành số lượng chain ít nhất.

Cận dưới.

Định nghĩa rank của một ước ~d~ là ~r(d)=e_1+e_2+\cdots+e_m~.

Tất cả các ước có cùng rank tạo thành một antichain. Thật vậy, giả sử ~x \mid y~ và ~r(x)=r(y)~. Vì mọi tọa độ của ~x~ đều không lớn hơn tọa độ tương ứng của ~y~, đồng thời tổng các tọa độ của chúng bằng nhau, nên tất cả các tọa độ phải bằng nhau. Do đó ~x=y~.

Vì vậy, các ước có cùng rank không thể được đặt trong cùng một chain. Do đó đáp án phải ít nhất bằng số lượng lớn nhất các ước có cùng rank.

Ý tưởng thuật toán.

Ta sẽ xây dựng một symmetric chain decomposition.

Ban đầu, trước khi thêm bất kỳ thừa số nguyên tố nào, ta chỉ có một chain là ~[1]~.

Giả sử ta đã có một cách phân chia hợp lệ cho một số thừa số nguyên tố đã xử lý. Xét một chain ~C=[c_0,c_1,\ldots,c_L]~, trong đó ~c_0 \mid c_1 \mid \cdots \mid c_L~.

Bây giờ ta thêm một thừa số nguyên tố mới ~p^a~. Ta cần phủ tất cả các số có dạng ~c_i p^j~, trong đó ~0 \le i \le L~ và ~0 \le j \le a~.

Với mỗi ~s=0,1,\ldots,\min(L,a)~, ta tạo một chain mới:

$$c_s p^0,\ c_s p^1,\ \ldots,\ c_s p^{a-s},\ c_{s+1}p^{a-s},\ c_{s+2}p^{a-s},\ \ldots,\ c_Lp^{a-s}.$$

Phần đầu của chain này hợp lệ vì số mũ của ~p~ tăng dần. Phần sau hợp lệ vì ~c_s \mid c_{s+1} \mid \cdots \mid c_L~. Do đó, mọi dãy được tạo ra đều là một chain.

Vì sao thuật toán này phủ mọi phần tử đúng một lần?

Xét một phần tử bất kỳ ~c_i p^j~.

Nếu ~i+j \le a~, thì phần tử này xuất hiện trong chain với ~s=i~.

Nếu ~i+j>a~, thì phần tử này xuất hiện trong chain với ~s=a-j~.

Vì vậy, mỗi phần tử xuất hiện trong ít nhất một chain. Hai trường hợp trên cũng xác định ~s~ một cách duy nhất, nên không có phần tử nào bị lặp. Do đó, sau khi xử lý ~p^a~, ta vẫn có một cách phân chia hợp lệ thành các chain.

Vì sao số lượng chain là tối ưu?

Thuật toán trên tạo ra một symmetric chain decomposition của lưới các ước.

Mỗi chain bắt đầu tại một rank ~r~ và kết thúc tại rank ~A-r~, trong đó ~A=a_1+a_2+\cdots+a_m~. Do đó, mỗi chain chứa đúng một ước ở rank giữa, nơi số lượng ước là lớn nhất.

Như đã chứng minh ở phần cận dưới, tất cả các ước có cùng rank tạo thành một antichain, nên cần ít nhất bấy nhiêu chain. Vì thuật toán của ta tạo ra đúng số lượng chain như vậy, nên nó là tối ưu.

Các bước thực hiện.

1. Phân tích ~n~ thành các lũy thừa nguyên tố.

2. Bắt đầu với một chain ~[1]~.

3. Với mỗi lũy thừa nguyên tố ~p^a~:

   • tính trước ~1,p,p^2,\ldots,p^a~;

   • với mỗi chain hiện tại ~C=[c_0,c_1,\ldots,c_L]~;

   • thay nó bằng các chain được mô tả ở trên.

4. In ra danh sách các chain cuối cùng.

Vì ~n \le 10^{18}~, ta có thể phân tích thừa số nguyên tố bằng kiểm tra nguyên tố Miller-Rabin và thuật toán phân tích Pollard Rho.

Độ phức tạp.

Phần phân tích thừa số sử dụng Miller-Rabin và Pollard Rho. Miller-Rabin cần ~O(\log n)~ phép nhân modulo cho mỗi cơ sở kiểm tra, và với số nguyên ~64~ bit, ta chỉ cần một số lượng hằng số các cơ sở.

Pollard Rho là một thuật toán ngẫu nhiên, nên thời gian chạy trong trường hợp xấu nhất thường không được chặn chặt trong phân tích thi đấu lập trình. Tuy nhiên, thời gian kỳ vọng để tìm một ước không tầm thường thường được ước lượng khoảng ~O(n^{1/4})~ trong các trường hợp khó. Với ~n \le 10^{18}~, phần này đủ nhanh trong thực tế.

Sau khi tìm được một ước không tầm thường, ta tiếp tục phân tích đệ quy hai phần thu được. Tổng số lần tách đệ quy là nhỏ vì số lượng thừa số nguyên tố của một số nguyên ~64~ bit là có giới hạn. Do đó, phần phân tích thừa số không phải là nút thắt so với việc in ra toàn bộ các ước.

Gọi ~\tau(n)~ là số lượng ước của ~n~ và ~\omega(n)~ là số lượng thừa số nguyên tố phân biệt của ~n~.

Với ~n \le 10^{18}~, ta có ~\omega(n) \le 15~, vì tích của ~16~ số nguyên tố đầu tiên đã lớn hơn ~10^{18}~. Ngoài ra, giá trị lớn nhất có thể của ~\tau(n)~ trong phạm vi này không vượt quá ~103680~, nên kích thước output là có thể xử lý được.

Thuật toán xử lý tất cả các ước đã sinh ra một lần cho mỗi thừa số nguyên tố phân biệt. Vì vậy, độ phức tạp thời gian là ~O(\tau(n)\omega(n))~, và độ phức tạp bộ nhớ là ~O(\tau(n))~.

#include<bits/stdc++.h>
using namespace std;

using ull = unsigned long long;
ull mod_mul(ull a, ull b, ull M){
    long long res = a * b - M * ull(1.L / M * a * b);
    return res + M * (res < 0) - M * (res >= (long long)M);
}
ull mod_pow(ull b, ull e, ull mod){
    ull res = 1;
    for(; e; b = mod_mul(b, b, mod), e >>= 1) if(e & 1) res = mod_mul(res, b, mod);
    return res;
}
// Millar Rabin Primality Test
// 7 times slower than a^b mod c
bool is_prime(ull n){
    if(n < 2 || n % 6 % 4 != 1) return (n | 1) == 3;
    ull s = __builtin_ctzll(n - 1), d = n >> s;
    for(ull a: {2, 325, 9375, 28178, 450775, 9780504, 1795265022}){
        ull p = mod_pow(a, d, n), i = s;
        while(p != 1 && p != n - 1 && a % n && i --) p = mod_mul(p, p, n);
        if(p != n - 1 && i != s) return false;
    }
    return true;
}
// Pollard rho algorithm
// O(n^{1/4})
ull get_factor(ull n){
    auto f = [n](ull x){ return mod_mul(x, x, n) + 1; };
    ull x = 0, y = 0, t = 30, prd = 2, i = 1, q;
    while(t ++ % 40 || __gcd(prd, n) == 1){
        if(x == y) x = ++ i, y = f(x);
        if(q = mod_mul(prd, max(x, y) - min(x, y), n)) prd = q;
        x = f(x), y = f(f(y));
    }
    return __gcd(prd, n);
}
// Returns {p, e} in increasing order of p
vector<ull> factorize(ull n){
    assert(n > 0);
    auto recurse = [&](auto self, ull n)->vector<ull>{
        if(n == 1) return {};
        if(is_prime(n)) return {n};
        ull x = get_factor(n);
        auto l = self(self, x), r = self(self, n / x);
        l.insert(l.end(),r.begin(),r.end());
        return l;
    };
    return recurse(recurse, n);
}

#define int long long

void solve(){
    int n;cin >> n;
    vector<ull> f=factorize(n);
    map<int,int> g;
    for(int x:f) g[x]++;

    vector<vector<int>> S={{1}};
    auto add = [&](int x,int d){
        vector<vector<int>> nS;
        for(auto v:S){
            int m=(int)v.size();
            for(int i=0;i<min(d+1,m);i++){
                vector<int> nv;

                int cur=v[i];
                for(int j=0;j<=d-i;j++){
                    if(j) cur*=x;
                    nv.push_back(cur);
                }
                for(int j=i+1;j<m;j++){
                    cur*=v[j]/v[j-1];
                    nv.push_back(cur);
                }

                nS.push_back(nv);
            }
        }
        swap(S,nS);
    };
    for(auto [x,d]:g) add(x,d);
    cout << (int)S.size() << '\n';
    for(auto v:S){
        cout << (int)v.size() << ' ';
        for(int x:v) cout << x << ' ';
        cout << '\n';
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int test;cin >> test;
    while(test--) solve();
}