【LG4397】[JLOI2014]聪明的燕姿

题面

洛谷

题解

考虑到约数和函数\(\sigma = \prod (1+p_i+...+p_i^{r_i})\)，直接爆搜把所有数搜出来即可。

爆搜过程和这道题一样，这里不再赘述。

代码

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

const int MAX_N = 1e5 + 5;

int prime[MAX_N], num;

bool nprime[MAX_N];

void sieve() {

	for (int i = 2; i <= 1e5; i++) {

		if (!nprime[i]) prime[++num] = i;

		for (int j = 1; j <= num && prime[j] * i <= 1e5; j++) {

			nprime[prime[j] * i] = 1;

			if (i % prime[j] == 0) break;

		}

	}

}

int Prime(int x) {

	if (x <= 1e5) return !nprime[x];

	for (int i = 1; i <= num && prime[i] * prime[i] <= x; i++)

		if (!(x % prime[i])) return 0;

	return 1;

}

int ans[MAX_N], cnt;

void solve(int S, int n, int lst) {

	if (S - 1 > prime[num] && Prime(S - 1)) ans[++cnt] = n * (S - 1);

	for (int i = lst; i; i--) {

		int sum = 1, times = prime[i];

		for (; sum + times <= S; ) {

			sum += times;

			if (S % sum == 0) solve(S / sum, n * times, i - 1);

			if (1ll * times * prime[i] <= 1ll * S) times *= prime[i];

			else break;

		}

	}

	if (S == 1) ans[++cnt] = n;

}

int S;

int main () {

#ifndef ONLINE_JUDGE

    freopen("cpp.in", "r", stdin);

	freopen("cpp.out", "w", stdout);

#endif

	sieve();

	while (scanf("%d", &S) != EOF) {

		cnt = 0;

		solve(S, 1, num);

		sort(&ans[1], &ans[cnt + 1]);

		printf("%d\n", cnt);

		for (int i = 1; i <= cnt; i++) printf("%d ", ans[i]);

		if (cnt) putchar('\n');

	}

    return 0;

}