题意
给出一个数 (S) ，输出所有约数和等于 (S) 的数。
(S le 2 imes 10^9) ，数据组数 (le 100) 。
题解
首先用约数和定理：
[egin{align}
n &= prod_{i} p_i^{a_i} \
Rightarrow sigma(n) &= prod_{i} (sum_{j=0}^{a_i} p_i^j)
end{align}
]
那么，我们可以通过从小到大来枚举质数 (p_i) 及其指数 (a_i) 来搜索。
-
若当前需要得到的 (S) 可以表示为一个未搜索过的质数与 (1) 的和，那么之前的数与这个质数的乘积是一个合法答案。
-
对于每一个使得 ((p + 1) imes (p + 1) < S) 的 (p) ，枚举可能的 (a_i) ，递归。
因为在第一种情况会把 (a_i = 1) 的特判掉（这种数出现并且仅出现一次），然后剩下的 (a_i ge 2) ，所以至少为 (1 + p + p ^ 2) 。
最后当一直除到 (1) 的时候就是答案了qwq
最开始随便用筛法筛素数就行了，复杂度 (O(pass)) 。。。
总结
对于约数和之类的题，考虑对于 (a_i = 1) 与 (a_i ge 2) 的情况分别考虑就行了，前者只存在一个，后者 (le sqrt p) 。
代码
随便看看实现就行了。。跑的速度还行qwq
#include <bits/stdc++.h>
#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)
#define Set(a, v) memset(a, v, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define debug(x) cout << #x << ": " << (x) << endl
#define DEBUG(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
using namespace std;
template<typename T> inline bool chkmin(T &a, T b) {return b < a ? a = b, 1 : 0;}
template<typename T> inline bool chkmax(T &a, T b) {return b > a ? a = b, 1 : 0;}
inline int read() {
int x(0), sgn(1); char ch(getchar());
for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;
for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);
return x * sgn;
}
void File() {
#ifdef zjp_shadow
freopen ("2234.in", "r", stdin);
freopen ("2234.out", "w", stdout);
#endif
}
set<int> S;
const int Maxn = sqrt(2e9);
bitset<Maxn + 5> is_prime;
void Math_Init(int maxn) {
is_prime.set();
is_prime[0] = is_prime[1] = false;
For (i, 2, maxn) if (is_prime[i])
for (int j = i * 2; j <= maxn; j += i) is_prime[j] = false;
}
inline bool Judge(int x) {
if (x <= Maxn) return is_prime[x];
for (int i = 2; i * i <= x; ++ i)
if (!(x % i)) return false;
return true;
}
void Dfs(int x, int cur, int pre) {
if (x == 1) { S.insert(cur); return ; }
if (x - 1 > pre && Judge(x - 1))
S.insert(cur * (x - 1));
For (p, pre + 1, sqrt(x + .5))
if (is_prime[p]) {
int sum = p + 1, here = p;
while (sum <= x) {
if (!(x % sum))
Dfs(x / sum, cur * here, p);
here *= p; sum += here;
}
}
}
int main () {
File();
Math_Init(Maxn);
int x;
while (~scanf("%d", &x)) {
S.clear(); Dfs(x, 1, 1);
printf ("%d
", (int)S.size());
for (int cur : S) printf ("%d ", cur);
if ((bool)S.size()) putchar ('
');
}
return 0;
}