亲和数
测试数据来自 system/1229
作业已超过截止时间,您无法递交本题目。
时间限制:1秒 内存限制:256M
【问题描述】
亲和数:定义数对 \((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\) 的情况。
任务:编写一个程序计算 \(A\) 到 \(B\) 范围内的亲和数对的数量。注意亲和数对 \((x,y)\) 必须满足 \(A≤x<y≤B\)。
【输入格式】
输入正整数 \(A\) 和 \(B\),中间用一个空格分开 。
【输出格式】
只有一行,就是 \([A,B]\) 内亲和数对的数量。
【输入输出样例】
Input
200 2000
Output
2
【输入输出样例说明】
在 200~2000 范围的亲和数有:(220, 284) 和 (1184,1210)。
【数据限制】
对于 \(50\%\) 数据:\(1 ≤ A ≤ B ≤ 100000\)
对于 \(80\%\) 的数据:\(1 ≤ A ≤ B ≤ 1000000\)
对于 \(100\%\) 的数据:\(1 ≤ A ≤ B ≤ 5000000\)