聪明的燕姿(约数和,爆搜)

聪明的燕姿(约数和,爆搜)

聪明的燕姿

题目链接
城市中人们总是拿着号码牌，不停寻找，不断匹配，可是谁也不知道自己等的那个人是谁。
可是燕姿不一样，燕姿知道自己等的人是谁，因为燕姿数学学得好！
燕姿发现了一个神奇的算法：假设自己的号码牌上写着数字 S，那么自己等的人手上的号码牌数字的所有正约数之和必定等于 S。
所以燕姿总是拿着号码牌在地铁和人海找数字（喂！这样真的靠谱吗）。
可是她忙着唱《绿光》，想拜托你写一个程序能够快速地找到所有自己等的人。

输入格式

输入包含 k 组数据。
对于每组数据，输入包含一个号码牌 S。

输出格式

对于每组数据，输出有两行。
第一行包含一个整数 m，表示有 m 个等的人。
第二行包含相应的 m 个数，表示所有等的人的号码牌。
注意：你输出的号码牌必须按照升序排列。

数据范围

1≤k≤100,
1≤S≤2×10⁹

输入样例：

42

输出样例：

3
20 26 41

算法分析

约数的基本定理
约数个数 (a₁+1)(a₂+1)…(a_k+1);
约数和    (1+p₁¹+p₁²+…p₁ ^a1)(1+p₂+…+p₂^a2)(1+p_k¹+p_k^ak);
a1,a2代表的是每个对应质因子的个数
p₁,p₂代表的是每个对应的质因子
对于S = 42来说，42对应的结果里面20，20 = (1 + 2 + 4 + 5 + 10 + 20)
20 = 2²*5
对于两个质因数2和5来说
2可以取0,1,2次，5可以取0,1次
所以S = (1+2¹+2²)(1+5¹) = 42
其中a₁=2,a₂=5,p₁=2,p₂=5;
这个题为什么可以暴力呢是因为每个质因子都按1算的话就是13!都有6e9那么多了,超过范围了,所以一次爆搜时间其实没有那么多.
我们去dfs搜索,记录上一次的质数下标,还有当前合数,还有剩余的s
当s==(1+p_i)只剩这一项的时候,就说明可以求出答案了.或者说s==1了也是除完了直接有答案了.
其余情况遍历质数,如果s能够除以当前质数的(1+p¹+…+pⁿ)时候,我们就除以该数,然后dfs进行下一步

代码实现

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn=5e4+5;
int pri[maxn],cnt;		//记录质数
bool vis[maxn];			//记录该数是否为质数
int ans[maxn],len;		//记录答案和答案个数
void oula()			//筛素数
{for(int i=2;i<=maxn;i++){if(!vis[i]){pri[cnt++]=i;}for(int j=0;pri[j]*i<=maxn;j++){vis[pri[j]*i]=true;if(i%pri[j]==0)break;}}
}
bool ispri(int x)		//这一步是为了x大于maxn我们没有求出来的质数的时候判断是否为质数
{if(x<maxn)return !vis[x];for(int i=2;i<=x/i;i++){if(x%i==0)return false;}return true;
}
void dfs(int last,int res,int s)		//last为上一个质数下标,res为当前合数,s为剩余乘积
{if(s==1)		//s就剩1了说明除完了{ans[len++]=res;return ;}if(last==-1)	//这一步是判断s<=3的时刻,如果不加这一步,s==3或2的时候是没有答案的{if(ispri(s-1)){ans[len++]=s-1;}}else			//看一下剩余s是否等于(1+p)的形式{if(s>pri[last]+1&&ispri(s-1)){ans[len++]=res*(s-1);}}for(int i=last+1;pri[i]<=s/pri[i];i++){int p=pri[i];int t=p;for(int j=1+p;j<=s;j+=t){if(s%j==0)dfs(i,res*t,s/j);t*=p;	//t为p次方数}}}
int main()
{int s;oula();while(cin>>s){len=0;dfs(-1,1,s);			//从-1开始是为了特判s==2或3的情况cout<<len<<endl;if(len){sort(ans,ans+len);for(int i=0;i<len;i++)cout<<ans[i]<<' ';cout<<endl;}}
}