题目描述
阴天傍晚车窗外
未来有一个人在等待
向左向右向前看
爱要拐几个弯才来
我遇见谁会有怎样的对白
我等的人他在多远的未来
我听见风来自地铁和人海
我排着队拿着爱的号码牌
城市中人们总是拿着号码牌，不停寻找，不断匹配，可是谁也不知道自己等的那个人是谁。可是燕姿不一样，燕姿知道自己等的人是谁，因为燕姿数学学得好！燕姿发现了一个神奇的算法：假设自己的号码牌上写着数字S，那么自己等的人手上的号码牌数字的所有正约数之和必定等于S。
所以燕姿总是拿着号码牌在地铁和人海找数字（喂！这样真的靠谱吗）可是她忙着唱《绿光》，想拜托你写一个程序能够快速地找到所有自己等的人。
输入
输入包含k组数据（k<=100）
输出
对于每组数据，输出有两行，第一行包含一个整数m，表示有m个等的人，第二行包含相应的m个数，表示所有等的人的号码牌。注意：你输出的号码牌必须按照升序排列。
样例输入
42
样例输出
3
20 26 41
提示
对于100%的数据，有S<=2*10*9
题解
一道显而易见的数学题，显而易见地我不会做。因为根本这个正解要用到的约数定理、约数和定理。唯一分解定理我都没学过，如果知道这些结论的话有没有推出答案的数学能力也未必。
唯一分解定理：
任何一个大于1的自然数N，都可以唯一分解成有限个质数的乘积N=P1^a1*P2^a2*…*Pn^an，这里P1<P2<…<Pn均为质数，其诸指数ai是正整数。这样的分解称为N的标准分解式。
约数和定理：
对于任意一个大于1的正整数N可以分解正整数：N=P1^a1*P2^a2…Pn^an，则由约数个数定理可知N的正约数有(a1+1)(a2+1)(a3+1)…(an+1)个，那么N的(a1+1)(a2+1)(a3+1)…(an+1)个正约数的和为f(N)=(P1^0+P1^1+P1^2+…P1^a1)(P2^0+P2^1+P2^2+…P2^a2)…(Pn^0+Pn^1+Pn^2+…Pn^an)。
用搜索将n分解为(p1^0+p1^1+…+p1^k1)(p2^0+p2^1+…+p2^k2)……(pn^0+pn^1+…+pn^kn),每一次成功的分解都会产生一个答案p1^k1*p2^k2*……*pn^kn。
搜索是很可行的。ad爷讲到对本题搜索的时间复杂度分析，当搜索的复杂度到了根号下根号n级别后就已经可以忽略了(高阶小量)，所以对这种搜索的时间复杂度只用考虑前几层。考试时常打搜索，有时接近正解，有时T得厉害，如果能学会这些分析应该会对搜索有更准确的估计吧。搜索之前要先处理出需要范围内的素数，还要有一个判断是否素数的函数。在搜索中要传递的是枚举到哪个素数(要求素数递增)、已有的乘积和、余下的需要分解的数。在搜索函数内先枚举素数，再枚举乘方，枚举到可以整除的就向下搜索。搜索停止的条件一是分解到只剩1，二是分解到一个大素数+1(直接在此处停止可以省去许多本来没有必要的枚举)。
数学问题确实千古难题，不管是奥赛还是文化课。到底是哪里难，也说不出个一二三。破釜沉舟，誓死不向数学低头。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const int sj=;
ll s,m,ps,p[],res[sj],ge;
bool fp[sj]={,};
void xxs()
{
for(int i=;i<;i++)
{
if(!fp[i])
{
ps++;
p[ps]=i;
}
for(int j=;j<=ps&&i*p[j]<sj-;j++)
{
fp[i*p[j]]=;
if(!(i%p[j]))
break;
}
}
}
int pss(ll x)
{
if(x==) return ;
for(int i=;p[i]*p[i]<=x;i++)
if(!(x%p[i]))
return ;
return ;
}
void dfs(int l,ll ji,ll yu)
{
if(yu==)
{
ge++;
res[ge]=ji;
return;
}
long long temp,f;
if((yu-)>p[l]&&pss(yu-))
{
ge++;
res[ge]=(yu-)*ji;
}
for(int i=l+;p[i]*p[i]<=yu;i++)
{
temp=;
f=;
for(int j=;temp<=yu;j++)
{
f*=p[i];
temp+=f;
if((yu%temp)==)
dfs(i,ji*f,yu/temp);
}
}
}
void cz()
{
while(scanf("%lld",&s)==)
{
memset(res,,sizeof(res));
ge=;
dfs(,,s);
if(ge!=)
{
sort(res+,res+ge+,less<int>());
printf("%lld\n",ge);
for(int i=;i<ge;i++)
printf("%lld ",res[i]);
printf("%lld\n",res[ge]);
}
else
printf("0\n");
}
}
int main()
{
xxs();
cz();
return ;
}