#pragma GCC optimize("Ofast")
#pragma GCC target("avx2,sse2,sse,avx,tune=native")
#pragma GCC optimize("unroll-loops")
#pragma GCC comment("/STACK:26666666")
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace __gnu_pbds;
#define pb push_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
using namespace std;
using ll = long long;
using vi = vector<int>;
const int mod = 1e9 + 7;
int n;
int cnt = 0, dcnt = 0, anscnt = 0;
bitset<1200200> vis[1345];//exact upper bound +1
bitset<6969569> vis2[1345];//exact upper bound +1
bitset<1000000001> good;
int ans[80808], go[10203];
int a[50000001], b[50000001], sz = 0;
int x, z, zz;
ll u;
__attribute__((always_inline)) inline bool mark(int i, int cur) {
x = 0;
for(int z = 1<<10; z; z>>=1)
if(x+z<dcnt&&go[x+z]<=i) x+=z;
z = (3ll*cur + 1)%1002523;
zz = (65ll*cur + 2)%6969569;
if(vis[x][z]&&vis2[x][zz]) return false;
vis[x][z] = 1;
vis2[x][zz] = 1;
return true;
}
__attribute__((always_inline)) inline void dfs(int i, int cur) {
if(i>n) return;
cnt++;
if(i == n) {
ans[anscnt++] = cur;
return;
}
for(int k = 0; k < dcnt; k++) {
u = i*1ll*go[k];
if(u>n) break;
if(good.test(u)&&mark(u, cur+go[k]-1)){
a[sz] = u;
b[sz] = cur+go[k]-1;
sz++;
}
}
}
__attribute__((always_inline)) void solve() {
a[0] = 1;
b[0] = 0;
mark(1, 0);
sz = 1;
int i = 0;
while(i < sz) {
dfs(a[i], b[i]);
i++;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n;
ll tn = n;
for(ll i = 1; i*i <= tn; i++) {
if(tn%i) continue;
if(i>1) {
go[dcnt++] = i;
good.set(i);
}
if(i*i!=n)
go[dcnt++] = n/i, good.set(n/i);
}
sort(go, go+dcnt);
solve();
// cerr<< cnt << "\n";
sort(ans, ans+anscnt);
cout << anscnt << "\n";
string s;
for(int i = 0; i < anscnt; i++)
s += to_string(ans[i]), s.pb(' ');
cout << s;
}
Compilation message
Compilation timeout while compiling toy
