题面
传送门 https://loj.ac/problem/2234
分析
看到约数之和, 我们首先想到约数和公式
若 $ x=\prod_{i=1}^{n}p_i^{k_i} \(, 则 x 的约数和为 \) \prod_{i=1}^{n} \sum_{j=0}^{k_i} p_i^j$
那么我们可以 DFS 枚举 x 的质因数分解式, 然后判断求出的约数和是否等于 s
具体来说, 我们先枚举选的质数 \(p_i\), 对于每个 \(p_i\) 枚举他们的指数 \(k_i\)(指数为 0 相当于不选), 然后计算和 \(tmp=1+p_i+p_i^2+\dots+p_i^{k_i}\)
然后将 tmp 乘入当前约数和
dfs(deep,left,ans) 表示当前枚举到第 deep 个质数, left 表示 s / 当前和, ans 表示当前的 x
注意剪枝:
1. 枚举质数时注意只需枚举 1~sqrt(s) 之间的质数, 然后如果 left 正好等于一个大质数 + 1, 则直接更新答案
质数的判断用 \(O(\sqrt n)\) 的试除法即可
2. 枚举和时, 当且仅当 left 能整除当前和的时候才继续更新
3. 不要用 sqrt 函数, 会很慢
代码
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- #include<cmath>
- #include<algorithm>
- #define maxn 100000
- using namespace std;
- long long s;
- int cnt=0;
- int vis[maxn+5];
- int prime[maxn+5];
- void sieve(int n){
- for(int i=2;i<=n;i++){
- if(!vis[i]) prime[++cnt]=i;
- for(int j=1;j<=cnt&&i*prime[j]<=n;j++){
- vis[i*prime[j]]=1;
- if(i%prime[j]==0) break;
- }
- }
- }
- bool is_prime(int x){
- if(x==1) return 0;
- if(x<=maxn) return !vis[x];
- else{
- for(int i=1;i<=cnt&&(long long)prime[i]*prime[i]<=x;i++){
- if(x%prime[i]==0) return 0;
- }
- return 1;
- }
- }
- int sqs;
- int sz=0;
- long long res[maxn];
- void dfs(int deep,long long left,long long ans){
- if(left==1){
- res[++sz]=ans;
- return;
- }
- if(left-1>prime[deep]&&is_prime(left-1)) res[++sz]=ans*(left-1);
- for(int i=deep+1;prime[i]*prime[i]<=left;i++){
- long long tmp=1;
- long long pow=1;
- for(int j=1;tmp+pow<=left;j++){
- pow*=prime[i];
- tmp+=pow;
- if(left%tmp==0) dfs(i,left/tmp,ans*pow);
- }
- }
- }
- int main(){
- sieve(maxn);
- while(scanf("%lld",&s)!=EOF){
- sz=0;
- dfs(0,s,1);
- printf("%d\n",sz);
- sort(res+1,res+1+sz);
- for(int i=1;i<=sz;i++){
- printf("%d",res[i]);
- }
- printf("\n");
- }
- }
来源: http://www.bubuko.com/infodetail-2927447.html