제출 #483233

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
483233		Monarchuwu	Toys (CEOI18_toy)	C++17	100 / 100	2055 ms	86728 KiB

toy

/**
 *  - x món 1, y món 2, z món 3 thì số cách chọn là (x + 1) * (y + 1) * (z + 1)
 *    => phân tích n thành tsnt, đặt s[i] là tập số lượng đồ chơi có thể chia thỏa trong i ngày
 *  - dp[i] += (dp[i / k] + k-1) (số món tăng k-1) (k là ước > 1 của i)
**/
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
using namespace std;
typedef long long ll;
int n;

vector<int> divisor(int n) {
    vector<int> div(1, n);
    for (int i = 2; i * i <= n; ++i) if (n % i == 0) {
        div.push_back(i);
        if (i * i != n) div.push_back(n / i);
    }
    return div;
}

map<int, set<int>> mp;
void calc(int n) {
    vector<int> div = divisor(n);
    for (int k : div) {
        if (!mp.count(n / k)) calc(n / k);
        for (int i : mp[n / k])
            mp[n].insert(i + k - 1);
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> n;

    mp[1].insert(0);
    calc(n);

    cout << mp[n].size() << '\n';
    for (int i : mp[n]) cout << i << ' ';
    cout << '\n';
}
/**  /\_/\
 *  (= ._.)
 *  / >0  \>1
**/

• Subtask 1: 19 / 19
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 21 / 21