#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 = 4e6 + 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;
}
Compilation message
fib.cpp: In function 'int main()':
fib.cpp:10:36: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
10 | #define forn(i, n) for(ll i = 0; i < n; i ++)
......
54 | forn(i, divis.size() - 1) {
| ~~~~~~~~~~~~~~~~~~~
fib.cpp:54:5: note: in expansion of macro 'forn'
54 | forn(i, divis.size() - 1) {
| ^~~~
fib.cpp:10:36: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
10 | #define forn(i, n) for(ll i = 0; i < n; i ++)
......
62 | forn(j, divis.size() - 1) {
| ~~~~~~~~~~~~~~~~~~~
fib.cpp:62:9: note: in expansion of macro 'forn'
62 | forn(j, divis.size() - 1) {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
3148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
3148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
1740 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
3148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
3148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
9 ms |
3148 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
