Perfect Numbers

1. Perfect Numbers
If number can be written as:a^m+b^n, where a,b>=1,
m,n>=2, we call it perfect number.

e.g., 1 is not a perfect number as there is no way to write 1
in this form.
2=1^2+1^2.Thus 2 is perfect number.
3 is not either.
4 is not.
5=1^2+2^2.thus5 is perfect number.

Find out how many numbers between 1-N are perfect
numbers. Example:
If N=1, return 0.
If N=2, return 1(2 is a perfect number)
If N=3, return(only 2 is a perfect number).
If N=5, return 2 (both 2 and 5 are perfect numbers).
…
N can be as large as 1,000,000.

 

解题思路：

a^m 可以看做一个矩阵 a行m列的矩阵

1^2 1^3 ……

2^2 2^3 ……

……

……

同理b^n，甚至和a^m可以试做同一个矩阵

矩阵上任意两个数相加，即为完美数字

最小数字a=1,m=2,per num=1+b^n

故求矩阵最大行列

行2^x-1<N-1 <= 2^x

列y-1^2<N-1<=y^2

得矩阵x * y

遍历矩阵取所有小于N的数，得数组A

循环A两次，取两数相加小于等于N的

 

源码下载

https://download.csdn.net/download/jine1987/14954663