[JLOI 2014] 聪明的燕姿（搜索剪枝）

[JLOI 2014] 聪明的燕姿（搜索剪枝）

文章目录

• 题目
• 分析
• 代码

题目

[JLOI 2014] 聪明的燕姿

分析

根据约数和定理 Dfs 即可，问题在于处理 S S S 的因数可能很大。
对于小于 S \sqrt S S ​ 的素数 p p p，可以筛出来然后暴力枚举 t t t，使得 ∑ i = 0 t p i ∣ S \sum_{i = 0}^{t} p^i \big| S ∑i=0t​pi∣∣​S ，对于大于 S \sqrt S S ​ 的素数 p p p 显然至多只有一个 p p p 能满足 1 + p ∣ S 1 + p \big| S 1+p∣∣​S，细节：注意枚举范围，并且要不重复地枚举，我们要求剩的部分（ 1 + p 1 + p 1+p）比之前枚举的都要大。

关于枚举范围，写完代码后可以看下 。

代码

#include <bits/stdc++.h>int Read() {int x = 0; char c = getchar();while (c < '0' || c > '9')c = getchar();while (c >= '0' && c <= '9')x = x * 10 + (c ^ 48), c = getchar();return x;
}const int SQRT = 1000000;int S;
std::vector<int> Ans;bool Vis[SQRT + 5];
int Pri[SQRT + 5], Cnt;bool IsPrime(const int &x) {if (x == 1) return false;if (x <= SQRT) return !Vis[x];for (int i = 1; Pri[i] * Pri[i] <= x; i++)if (x % Pri[i] == 0)return false;return true;
}void Dfs(const int &cur, const int &num, const int &p) {if (cur == 1) {Ans.push_back(num);return;}if (cur - 1 >= Pri[p] && IsPrime(cur - 1))Ans.push_back(num * (cur - 1));for (int i = p; i <= Cnt && 1 + Pri[i] + Pri[i] * Pri[i] <= cur; i++) {int bas = Pri[i], tot = Pri[i] + 1;while (tot <= cur) {if (cur % tot == 0)Dfs(cur / tot, num * bas, i + 1);tot += bas *= Pri[i];}}
}int main() {for (int i = 2; i <= SQRT; i++) {if (!Vis[i]) Pri[++Cnt] = i;for (int j = 1; j <= Cnt && i * Pri[j] <= SQRT; j++) {Vis[Pri[j] * i] = true;if (Pri[j] % i == 0) break;}}while (~scanf("%d", &S)) {Ans.clear();Dfs(S, 1, 1);std::sort(Ans.begin(), Ans.end());printf("%d\n", (int)Ans.size());for (int i: Ans)printf("%d ", i);if(Ans.size()) puts("");}return 0;
}