| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 481187 | hidden1 | Toys (CEOI18_toy) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#ifndef LOCAL
#define cerr if(false) cerr
#endif
#define endl "\n"
#define all(x) (x).begin(), (x).end()
#define forn(i, n) for(ll i = 0; i < n; i ++)
#define revn(i, n) for(ll i = n - 1; i >= 0; i --)
typedef long long ll;
template<class T, template<class T2, class A=allocator<T2> > class cont> inline ostream &operator <<(ostream &out, const cont<T> &x) { for(const auto &it : x) { out << it << " ";} return out;}
template<class T, template<class T2, class A=allocator<T2> > class cont> inline istream &operator >>(istream &in, cont<T> &x) { for(auto &it : x) { in >> it;} return in;}
template<class T, class T2> inline ostream &operator <<(ostream &out, const pair<T, T2> &x) { out << x.first << " " << x.second; return out;}
template<class T, class T2> inline istream &operator >>(istream &in, pair<T, T2> &x) { in >> x.first >> x.second; return in;}
template<class T, class T2> inline bool chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
template<class T, class T2> inline bool chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
const ll mod = 1e9 + 7;
const ll MAX_N = 1e7 + 10, MAX_CORD = 2e3 + 10;
ll n;
vector<ll> divis;
void comp(ll x) {
for(ll i = 1; i * i <= x; i ++) {
if(x % i == 0) {
divis.push_back(i);
if(i * i != x) {
divis.push_back(x / i);
}
}
}
sort(all(divis));
}
bitset<MAX_N> dp[MAX_CORD];
ll who[MAX_CORD][MAX_CORD];
signed main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
cin >> n;
if(n == 1) {
cout << 1 << endl << 0 << endl;
return 0;
}
comp(n);
dp[0][0] = true;
forn(i, divis.size() - 1) {
cerr << "Starting " << i << ": ";
forn(j, MAX_N) {
if(dp[i][j]) {
cerr << j << " ";
}
}
cerr << endl;
forn(j, divis.size() - 1) {
ll prod = divis[i] * divis[j];
ll to = -1;
if(n % prod == 0) {
to = lower_bound(all(divis), prod) - divis.begin();
} else {
continue;
}
cerr << "from " << divis[i] << " " << divis[j] << " -> " << divis[to] << endl;
dp[to] |= dp[i] << (divis[j] - 1);
}
}
cout << dp[divis.size() - 1].count() + 1 << endl;
forn(i, MAX_N) {
if(dp[divis.size() - 1][i]) {
cout << i << " ";
}
}
cout << n - 1 << endl;
return 0;
}