本文共 731 字,大约阅读时间需要 2 分钟。
任何正整数都可以表示为四个平方数之和。
4平方数情况:n = 4^k * ( 8*b + 7 )
2平方数情况:n = 4^k * ( a*a + b*b )
1平方数情况:n = 4^k * ( a*a )
3平方数情况:其他 class Solution {public: int numSquares(int n) { while( (n&3) == 0) n/=4; if( (n&7) == 7) return 4; int a = 0; const double eps = 0.000001; while(a*a < n){ int b = int(sqrt(n-a*a) + eps); if( a*a + b*b == n){ if(a != 0 && b != 0){ return 2; }else{ return 1; } } a++; } return 3; }};
一个很强的公式:
(a^2 + b^2 + c^2 + d^2)* (x^2 + y^2 + z^2 + w^2) = (ax + by + cz + dw)^2 + (ay - bx + cw -dz)^2 + (az - bw -cx + dy)^2 + (aw + bz - cy - dx)^2
转载地址:http://efwji.baihongyu.com/