今天晴天 » 日志 » P1216 亲和数 剪枝
P1216 亲和数 剪枝
Ronice 发表于 2006-10-18 18:36:49
描述 Description
这种数是——亲和数，所谓亲和数就是：
定义数对 (x,y) 为亲和数对当且仅仅当x、y为不同正整数，且x、y各自的所有非自身正因子之和等于另一个数。例如 (220,284) 和 (280,224) 都是亲和数对，因为：
220的所有非自身正因子之和为：1 + 2 + 4 + 5 + 10 + 11 + 20 + 22 + 44 + 55 + 110 = 284
284的所有非自身正因子之和为：1 + 2 + 4 + 71 + 142 = 220
数对 (x,y ) 跟 (y,x) 被认为是同一数对，所以我们只考虑 x<y 的情况。
任 务 ：tenshi对某个范围内的亲和数对的数量非常感兴趣，所以希望你能帮她编写一个程序计算给定范围内的亲和数对的数量。给定一个范围A到B，如果A≤ x ≤ B，则我们称 (x,y)在范围[A,B]内。
输入格式 Input Format
从文件的第一行分别读入正整数A和B，其中A、B满足
1 ≤ A ≤ B ≤ 10^8 且 B-A ≤ 10^5
输出格式 Output Format
输出文件只有一行，就是[A,B]内亲和数对的数量
评测机的差距好大……终于等到PuppyAC了，硬搜
限制条件评测结果的差异：
编译通过...(加了限制条件f(i)>i以及f(f(i))>i就跳出)
├ 测试数据 01：答案正确... 41ms
├ 测试数据 02、04、06、08 0ms
├ 测试数据 05：答案正确... 41ms
├ 测试数据 07：答案正确... 369ms
├ 测试数据 09：答案正确... 697ms
├ 测试数据 10：答案正确... 603ms
-------------------------
Accepted 有效得分：100 有效耗时：1751ms
编译通过...(限制条件再加上f(i)<i+100000)
├ 测试数据 01：答案正确... 41ms
├ 测试数据 02、03、04、06、08 0ms
├ 测试数据 05：答案正确... 41ms
├ 测试数据 07：答案正确... 369ms
├ 测试数据 09：答案正确... 697ms
├ 测试数据 10：答案正确... 588ms
-------------------------
Accepted 有效得分：100 有效耗时：1736ms
最新评论
-
2008-02-29 22:33:41 匿名 124.238.*.*
大哥你写题解就出来一堆f[i],f[f[i]],f[i]>i也没有程序对照教我怎么理解？
-
2008-03-01 01:11:45 匿名 61.164.*.*
这个…… 寒假的时候一直在颓废，然后觉得blog好久没有更新了，就贴几个出来…… 但是这个题解是很久以前就放上来的了啊～～～ 我想一下，我也不大记得了……
-
2008-03-01 01:19:54 匿名 61.164.*.*
我自己也没有程序，因为vijos挂了。。。看情况，应该是f(i)为i的非自身正因子之和，故若是亲和数，则f(f(i))=i；f(i)>i是因为这句话： 数对 (x,y ) 跟 (y,x) 被认为是同一数对，所以我们只考虑 x<y 的情况
