Welcome

首页 / 软件开发 / 数据结构与算法 / 双倍超立方数算法

双倍超立方数算法2010-01-28阿牛题目要求:双倍超立方数是指一个正整数可以正好被拆分为两种不同的a^3+b^3的方式,其中a,b均为整数且0<a<=b。对于任何一个指定的 int n, 返回所有的小于等于n的双倍超立方数的个数。

Definition
Class: TwiceSuperCubic
Method: count
Parameters: int
Returns: int
Method signature: int count(int n)
(be sure your method is public)

Constraints
- n取值范围为1到1,000,000,000(含)
Examples
0)
1

Returns: 0


1)
1729

Returns: 1
1729=1^3+12^3
1729=9^3+10^3


2)
475574

Returns: 27

因为题中大量使用3次方计算,这里我们也可以减少重复计算。原理公式为:

(n + 1)^2 = n^2 + 2n + 2
(n + 1)^3 = n^3 + 3n^2 + 3n + 1