Hlg 1563 亲合数.cpp memset

题意：

　　如果a的真因子之和 = b的真因子之和，则称a和b为亲合数，现在要找出100000以内的亲合数..

　　要求不出现重复的数对..

思路：

　　如果暴力找出100000以内所有数 (a) 的真因子和 (b) 然后看看这个和的真因子和(b)是否也等于这个数(a)..的话太暴力了..会tle..

　　所以可以利用 num = p0^a0*p1^a1*p2^a2...pn^an..即任何一个数都可以看作是素数 pi的n次幂乘以一个数..

　　所以pi的0次幂到n次幂*pj的0~n次幂*..都是num的真因子..

　　所以就是for循环找出所有的数的倍数加入到sum里面..

Tips：

　　这个真真吃了memset的亏了..

　　其实以前就知道memset中初始化的值应该用二进制表示..但是一直以来直接用10进制表示都没有错~所以就没注意到了..

　　结果把sum初始化为 1 的时候就出问题了..

　　果然~老人的话还是要听的..

Code：

View Code

 1 #include <iostream>
 2 #include <cstring>
 3 using namespace std;
 4 
 5 int sum[100010];
 6 int main()
 7 {
 8     int i, j, k;
 9     //memset(sum, 1, sizeof(sum));
10     for(i = 0; i < 100000; ++i)
11         sum[i] = 1;
12     for(i = 2; 2*i <= 100000; ++i) {
13         j = i*2;             ///j 从 i 的两倍开始算
14         while(j <= 100000) {
15             sum[j] += i;          ///j 既然是从 i * n得来的..则 i 也算是 j 的真因子了..
16             j += i;       
17         }
18     }
19     for(i = 220; i <= 100000; ++i)    ///题目给出了最小的亲合数对中较小的那个就是220了..
20     if(sum[i] > i && sum[i] <= 100000 && sum[sum[i]] == i) {
21         cout << i << ' ' << sum[i] << endl;
22     }
23     return 0;
24 }

题目链接：http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=1563