17115 ooxx numbers
时间限制:1000MS 内存限制:65535K
题型: 编程题 语言: 无限制
Description
a number A called oo number of a number B if the sum of all As factor is the number B.
(A,B) is a pair of ooxx numbers if A is the oo number of B and B is the oo number of A.
Now i want to find how many pairs of ooxx numbers in [1,n]
输入格式
there are many cases in the input.
for each line there is a number n. ( 1 <= n <= 5000000 )
输出格式
for each n, output the numbers of pairs of ooxx numbers in [1,n]
输入样例
300
1300
输出样例
1
2
提示
hits
220=1+2+4+71+142=284,
284=1+2+4+5+10+11+20+22+44+55+110=220。
220 and 280 is a pair of ooxx numbers.
作者
admin
解题思路
这题是华农13年校赛的其中一题，当初没有过，如果过了就有一等奖了，没想到这题是打表题，没有经验就想不到有这种处理方式，所以还是学到东西了，当时ZF牛打表出了点差错也没有过，回头很快的秒掉了，真的很快，这次重新写的时候还是Wa了，因为处理因子上出了点差错，将可开根的数的因子少算了一个，导致最后打出的表少了一个数据，跪了。还有一个比较傻逼的问题就是，打表就是打表，不用太在乎效率，没想到我连打表都尽量减少其运行的时间，好几个判断的条件，还是不小心折腾了一番，_(:з」∠)_
ZF大神求因子和的方法：筛素数的思维方式筛出因子和，每个i为因子，j为i的倍数，值得借鉴
相比之下自己求因子和的方法，太挫了 -_-||：
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<algorithm> using namespace std; int digit[]; int main()
{
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ;
digit[] = ; sort(digit, digit+);
int n;
while(scanf("%d", &n) != EOF)
{
int i = ;
for(; i<=; ++i)
if(digit[i] > n) break;
printf("%d\n", i-);
}
return ;
}