题解 | #小红构造数组#

首先对n分解质因数，找出质因数的数组，然后对该数组进行dfs，因为不能相邻所以每次跳过刚刚选择的数字，找到一个刚好整除的组合即可返回。

#include <iostream>
#include <set>
#include <vector>
#include <cmath>
using namespace std;

set<long long> prime;
vector<long long> arr;
vector<long long> ans;
bool findcombination = false;
//筛出所有质因数
void getprime(long long n) {
    // 筛掉所有偶数
    while (n % 2 == 0) {
        prime.insert(2);
        n /= 2;
    }
    // 筛奇数
    for (long long i = 3; i <= sqrt(n); i += 2) {
        while (n % i == 0) {
            prime.insert(i);
            n /= i;
        }
    }
    // 没整除完表示自身也是
    if (n > 2) {
        prime.insert(n);
    }
}
// 在质因数上做dfs组合，找到一个就停止
void dfs(long long pre, long long n) {
    // 找到了直接返回
    if (findcombination) {
        return;
    }
    // 整除了表示找到一个组合
    if (n == 1) {
        findcombination = true;
        ans = arr;
        return;
    }
    // dfs遍历质因数，对数组做剪枝
    for (auto& val : prime) {
        if (val == pre) {
            continue;
        }
        if (n % val == 0) {
            long long nextVal = n / val;
            arr.push_back(val);
            dfs(val, nextVal);
            arr.pop_back();
        }
    }
}
int main() {
    long long x;
    while (cin >> x) {
        //分解质因数
        getprime(x);
        findcombination = false;
        // 找一种组合
        dfs(-1, x);
        int n = ans.size();
        // 没找到-1；
        if (n == 0) {
            cout << -1 << endl;
        } else {
            cout << n << endl;
        }
        for (auto val : ans) {
            cout << val << " ";
        }
        cout << endl;
    }
}