[数据结构与算法]Easy Math Problem题解

题目链接：Problem - 1005 (hdu.edu.cn)

题目大意：如果一个数等于除自身之外所有的因数之和，则称这个数为完数；如果一个数可由除自身外的所有因数构成的集合中的某些元素构成的子集相加得到，则称这个数为半完数。给定一个整数p (1<p<1e9),求一整数a,要求a是半完数，a是p的倍数，并且1<a<2e18。

输入格式：输入一个正整数p。

输出格式：共两行，第一行输出a,及所选择的子集的大小。第二行输出该子集中的每一个数。

思路：根据半完数的定义，容易得到所有的完数都是半完数。假设a是完数，它除自身外的所有因子有p1,p2...pn,那么p1+p2+...+pn=a。而k*a的因子一定有k*p1,k*p2...k*pn,其之和为? k*p1+k*p2+...+k*pn=k*(p1+p2+...+pn)=k*a，即k*a一定为半完数。所以对于任意的输入p，只需要将一个完数乘以该数，并且保证乘积不大于2e18。而6=1+2+3，是一个完数，而6*p<6e9不会超出范围所以只需要输出6*p即可。

代码：

?
#include<bits/stdc++.h>
using namespace std;
int main(){
    long long p;
    int n;
    cin>>n;
    while(n--){
        scanf("%lld",&p);
        printf("%lld 3\n%lld %lld %lld\n",6*p,p,2*p,3*p);
    }
    return 0;
}

?