题目描述

城市中人们总是拿着号码牌，不停寻找，不断匹配，可是谁也不知道自己等的那个人是谁。

可是燕姿不一样，燕姿知道自己等的人是谁，因为燕姿数学学得好！

燕姿发现了一个神奇的算法：假设自己的号码牌上写着数字 S，那么自己等的人手上的号码牌数字的所有正约数之和必定等于 S。

所以燕姿总是拿着号码牌在地铁和人海找数字（喂！这样真的靠谱吗）。

可是她忙着唱《绿光》，想拜托你写一个程序能够快速地找到所有自己等的人。

输入格式

输入包含 k 组数据。

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

输出格式

对于每组数据，输出有两行。

第一行包含一个整数 m，表示有 m 个等的人。

第二行包含相应的 m 个数，表示所有等的人的号码牌。

注意：你输出的号码牌必须按照升序排列。

数据范围

1≤k≤100,
1≤S≤2×109

输入样例：

42

输出样例：

3
20 26 41

C++ 代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 50000;//只需要枚举sqrt(s)个即可

int primes[N], cnt;
bool st[N];//用于表示当前数是否被用过
int ans[N], len;//ans用于记录答案,len用于记录答案个数

//线性筛法求素数
void get_primes(int n){
    for(int i = 2; i <= n; i ++){
        if(!st[i]) primes[cnt ++] = i;
        for(int j = 0; primes[j] * i <= n; j ++){
            st[primes[j] * i] = true;
            if(i % primes[j] == 0) break;
        }
    }
}

//判断质数
bool is_prime(int x){
    if(x < 2) return false;
    for(int i = 2; i <= x / i; i ++){
        if(x % i == 0) return false;   
    }
    return true;
}

//last表示上次枚举的质数的下标,pres表示当前的值, s表示剩余的值
void dfs(int last, int pres, int s){
    if(s == 1){
        ans[len ++] = pres;
        return ;
    }

    //s = 1 + p的特殊情形        ----- 时间复杂度仅为根号级别
    if(s - 1 > (last < 0 ? 1 : primes[last]) && is_prime(s - 1)){
        ans[len ++] = pres * (s - 1);
    }

    //s = (1 + pi + pi ^ 2 + ···)(1 + pi + pi ^ 2 + pi ^3 ···)···的情形,pi ^ 2 <= s
    for(int i = last + 1; primes[i] <= s / primes[i]; i ++){
        int p = primes[i];
        for(int j = 1 + p, t = p; j <= s; t *= p, j += t){//用于计算当前()项的和
            if(s % j == 0) dfs(i, pres * t, s / j);
        }
    }
}

int main(){
    get_primes(N);

    int s;
    while(cin >> s){
        len = 0;
        dfs(-1, 1, s);

        cout << len << endl;
        if(len){
            sort(ans, ans + len);
            for(int i = 0; i < len; i ++) cout << ans[i] << ' ';
            cout << endl;
        }
    }
}