#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
long long summa = 0;
vector<long long> prs, much;
set<long long> ans;
vector<long long> chs;
vector<vector<long long>> step;
void f(long long i, long long m, long long pos) {
if (pos == summa - 1) {
chs[pos] *= step[i][m];
if (i + 1 < prs.size()) {
f(i + 1, much[i + 1], 0);
chs[pos] /= step[i][m];
}
else {
long long r = 0;
for (auto chch : chs) {
r += chch - 1;
}
ans.insert(r);
chs[pos] /= step[i][m];
}
}
else {
for (long long sta = 0; sta <= m; sta++) {
chs[pos] *= step[i][sta];
f(i, m - sta, pos + 1);
chs[pos] /= step[i][sta];
}
}
}
int main() {
long long n;
cin >> n;
if (n == 1) {
cout << 0;
return 0;
}
long long lim = 1e5;
vector<bool> prost(lim, 1);
long long nn = n;
for (long long i = 2; i < lim; i++) {
if (prost[i]) {
if (n % i == 0) {
prs.push_back(i);
long long muc = 0;
while (nn % i == 0) {
muc++;
nn /= i;
}
much.push_back(muc);
}
for (long long j = i * i; j < lim; j += i) {
prost[j] = 0;
}
}
}
if (nn > 1) {
prs.push_back(nn);
much.push_back(1);
}
for (auto z : much) {
summa += z;
}
chs.resize(summa, 1);
step.resize(prs.size(), vector<long long>(summa + 1, 1));
for (long long i = 0; i < prs.size(); i++) {
for (long long j = 1; j <= much[i]; j++) {
step[i][j] = step[i][j - 1] * prs[i];
}
}
f(0, much[0], 0);
cout << ans.size() << '\n';
for (auto as : ans) {
cout << as << " ";
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |