[bzoj 3629] [JLOI2014]聪明的燕姿

求正约数之和等于S的所有正整数. (S≤2e9, 多组数据, 不超过100组) 首先, 约数和是积性函数, 容易推导出这样一个公式:

然后, 枚举质因子, 和这个质因子的次数.

再然后, 就不会了TAT 看题解.

把S分解成素数的几何级数之积, 大于的素数至多用一个, 并且它的次数只能为1. 利用这个事实, 只用打不超过的素数表. DFS, 按照素数表从小到大枚举质因子和它的次数. 每一层额外判断一下, 是否能直接放上那个大于的素数+1. 方法是判断现在剩下的S的因子-1是否大于并且是素数.

这样就可以通过本题了, 但还可以继续优化.

设DFS时, 当前S剩下的因子为x, x同样满足前面所述的性质: 大于的素数至多用一个, 并且次数为1. 显然它只能是我们使用的最大的一个素数. 所以, 仍然在每层额外判断一下, (x-1)是否是素数. 还需要保证其最大性, 防止重复枚举. 另外, 判素数的时候可以利用已经打出来的素数表.

优化挺明显的: 4024ms -> 132ms

不错的一道题.

#include <bits/stdc++.h>
#define Rep(i, a, b) for (int i = (a), i##_ = (b); i < i##_; ++i)
#define For(i, a, b) for (int i = (a), i##_ = (b); i <= i##_; ++i)
#define Down(i, a, b) for (int i = (a), i##_ = (b); i >= i##_; --i)

using namespace std;
typedef long long ll;
const int MAX_P = 44722;
int cnt, num, prime[5000], ans[100000];

void sieve()
{
	static bool f[MAX_P + 1];
	For (i, 2, MAX_P) {
		if (!f[i])
			prime[num++] = i;
		for (int j = 0, k; j < num && (k = i * prime[j]) <= MAX_P; ++j) {
			f[k] = true;
			if (i % prime[j] == 0)
				break;
		}
	}
}

bool isprime(int n)
{
	if (n == 1) return false;
	for (int i = 0; i < num && prime[i]*prime[i] <= n; ++i)
		if (n % prime[i] == 0)
			return false;
	return true;
}

void solve(int x, int pos, int y)
{
	if (x == 1) {
		ans[cnt++] = y;
		return;
	}

	for (int p; pos < num && (p = prime[pos], p*p <= x); ++pos)
		for (ll z = p, s = 1 + z; s <= x; z *= p, s += z)
			if (x % s == 0)
				solve(x / s, pos + 1, y * z);

	if ((pos == num || x-1 >= prime[pos]) && isprime(x-1))
		ans[cnt++] = y * (x-1);
}

int main()
{
	sieve();
	int n;
	while (scanf("%d", &n) == 1) {
		cnt = 0;
		solve(n, 0, 1);
		sort(ans, ans + cnt);
		printf("%d\n", cnt);
		Rep (i, 0, cnt)
			printf("%d%c", ans[i], " \n"[i == cnt-1]);
	}
	return 0;
}