Ý tưởng

Ta cần tìm cách để thêm nhiều số nhất vào mảng ans kết quả của chúng ta.

Đầu tiên, ans = {N}

Dễ thấy, ta cần thêm tất cả các số nguyên tố từ 2 đến N (do các số bé hơn 2 ko thể nguyên tố) vào dãy ans. Do các số này đều là số nguyên tố nên dãy số ans sẽ luôn thỏa mãn.

Vậy còn "với mỗi a[i] thì a[i] là ước của 1 trong các số từ a[1] -> a[i-1]" thì sao? Ta thấy, các số nguyên tố luôn lớn hơn 2 và chỉ có 1 ước khác nó là 1. Vậy ta thêm 1 vào dãy ans. Ta không thể thêm bất kỳ số nào là ước khác của các số nguyên tố được thêm vào trước đó. Điều đó dẫn tới các số thêm vào chỉ còn có thể là ước của N.

Vậy tóm lại, ta cần thêm tất cả các SNT từ 1->N và tất cả các ước của N, sau đó xóa đi các phần tử bị lặp lại (sử dụng set) và sắp xếp lại dãy ans. Như vậy sẽ ra được kết quả.

Code (C++)

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

int isPrime(int n){
    // Khong can if(n < 2) return false do ta se khong xet toi n < 2
    if(n < 4) return true;
    for(int i=2;i*i<=n;i++)
        if(n % i == 0) return false;
    return true;
}

int main(){
    ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    freopen("DAYSO.IN","r",stdin);
    freopen("DAYSO.OUT","w",stdout);

    int n; cin >> n;
    set<int> ans = {n,1}; // luon co 1 trong day ans
    // Tim tat ca cac SNT tu 2->n-1 (khong can n do n da co trong ans)
    for(int i=2;i<n;i++)
        if(isPrime(i)) ans.insert(i);
    // Tim tat ca cac uoc cua n
    for(int i=2;i*i<=n;i++)
    if(n % i == 0) {ans.insert(i); ans.insert(n/i);}
    // Sap xep lai ans
    vector<int> out(ans.begin(),ans.end());
    sort(out.begin(),out.end(),greater<int>());
    // In ra kq
    for(int i: out) cout << i << ' ';
    return 0;
}