LOJ #2234. 「JLOI2014」聰明的燕姿 && 約數和、約數個數定理複習

#include <bits/stdc++.h>
#define

using namespace std;
typedef long long ll;
int bz[A], pri[A], cnt, s, p[A], k;
bool check(int x) {
  if (x < 100000) return !pri[x];
  int kj = sqrt(1.0 * x);
  for (int i = 2; i <= kj; i++) if (x % i == 0) return false;
  return true;
}
void dfs(int now, int x, int s) { //now是目前枚舉到了第幾個質數,x是前面的質數的積,s就是約數和
  if (s == 1) {p[++k] = x; return;}
  if (s - 1 > bz[now] and check(s - 1)) p[++k] = (s - 1) * x;
  int kj = sqrt(1.0 * s); //找根号s以内的質數，大了沒有意義反正統計不進答案
  for (int i = now + 1; i <= cnt and bz[i] <= kj; i++) {
    int tmp = bz[i];
    for (int j = tmp + 1; j <= s; tmp *= bz[i], j += tmp) if (s % j == 0) dfs(i, x * tmp, s / j);
  }
}

int main(int argc, char const *argv[]) {
  for (int i = 2; i <= 100000; i++) {
    if (!pri[i]) bz[++cnt] = i;
    for (int j = 1; j <= cnt and bz[j] * i < 100000; j++) {
      pri[i * bz[j]] = 1;
      if (i % bz[j] == 0) break;
    }
  }
  while (cin >> s) {
    k = 0; dfs(0, 1, s);
    sort(p + 1, p + k + 1);
    k = unique(p + 1, p + k + 1) - p - 1;
    printf("%d\n", k);
    for (int i = 1; i <= k; i++) printf("%d ", p[i]); puts("");
  }
  return 0;
}