中级农民
- 积分
- 128
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2011-2-8
- 最后登录
- 1970-1-1
|
又搜到一个结论: Every integer not of the form 4^a (8b+7) is the sum of three squares
没想到这题能用到这么多数学结论。于是有了O(sqrt(n))的办法:
- def solve(n):
- l = [];
- s1 = {};
- for i in xrange(1, n+1):
- if i * i > n:
- break;
- l.append(i);
- s1[i * i] = 1;
- if s1.has_key(n):
- return 1;
- for i in l:
- if s1.has_key(n - i * i):
- return 2;
- while(n % 4 ==0):
- n /= 4;
- if n % 8 != 7:
- return 3;
- return 4;
复制代码 |
|