原题目

题目描述:

自然数a的因子是指能整除a的所有自然数，但不含a本身。例如12的因子为：1、2、3、4、6。若自然数的因子之和为b，而且b的因子之和又等于a，则称a,b为一对“亲和数”。求最小的n对亲和数。

编写程序求最小的n对亲和数，每行输出一个（输出时严格按a升序输出）。

输入格式:

一个数，表示题目中的n。

输出格式:

共n行，每行表示一对亲和数。

样例输入:

样例输出:

6 6

提示:

60%的数据是n <= 20
100%的数据是n <= 40

时间限制:1000ms
空间限制:256MByte（摘自wzoi.cc）

解题

part1

好的，看起来枚举是个不错的选择。编了如下代码。

/*亲和数tradition by WT*/
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
int sum(int s)
{int su=1;for(int i=2;i<=s/2;i++){if(s%i==0)su+=i;}return su;
}
int main()
{int a,i=0,x=6,y=6;cin>>a;while(i<a){y=sum(x);if(sum(y)==x){cout<<x<<" "<<y<<endl;i++;}x++;}return 0;
}

提交。什么？竟然没有通过？一看：有两个TLE。

于是，我就大胆地试了一下输入“40”。

音乐都听完两首了，结果才输出完毕。

于是乎——枚举会超时，可不可以在本地计算完毕，存入数组，再输出呢？

part2

编了如下代码。

/*亲和数tradition by WT*/
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
int sum(int s)
{int su=1;for(int i=2;i<=s/2;i++){if(s%i==0)su+=i;}return su;
}
int main()
{int a,i=0,x=6,y=6;cin>>a;freopen("#qha.out","w",stdout);while(i<a){y=sum(x);if(sum(y)==x){cout<<x<<",";i++;}x++;}fclose(stdout);system("pause"); x=y=6;i=0;freopen("#qhb.out","w",stdout);while(i<a){y=sum(x);if(sum(y)==x){cout<<y<<",";i++;}x++;}fclose(stdout);return 0;
}

嘻——嘻——嘻——

计算以后，输出到屏幕上一个个抄到代码里太麻烦了。带逗号输出到.out文件里，复制一下，简直完美！

于是，我听了四首歌。

结果如下：

哈哈哈哈哈哈

兴奋极了！打开，果然都有啊！

part3

代码效果是这样的：

源代码在此：

/*亲和数tradition by WT*/
#include <iostream>
#include <cmath>
#include <cstdio>
using namespace std;
int a[40]={6,28,220,284,496,1184,1210,2620,2924,5020,5564,6232,6368,8128,10744,10856,12285,14595,17296,18416,63020,66928,66992,67095,69615,71145,76084,79750,87633,88730,100485,122265,122368,123152,124155,139815,141664,142310,153176,168730};
int b[40]={6,28,284,220,496,1210,1184,2924,2620,5564,5020,6368,6232,8128,10856,10744,14595,12285,18416,17296,76084,66992,66928,71145,87633,67095,63020,88730,69615,79750,124155,139815,123152,122368,100485,122265,153176,168730,141664,142310};
int main()
{int n;cin>>n;for(int i=0;i<n;i++)cout<<a[i]<<" "<<b[i]<<endl;return 0;
}

哈哈哈哈哈笑（ku）到手抖啊！

果然。100分。

大家没事不要学我。脑子（我指，呃，电脑）会学坏掉的。

欢迎点评！