Sums of Perfect Squares

题面:CodeWars / LeetCode 一样的题

输入一个正整数 n (3 < n < 109),找到它最少由多少个完全平方数组成。

样例:

sum_of_squares(17) == 2; // 17 = 16 + 1
sum_of_squares(15) == 4; // 15 = 9 + 4 + 1 + 1
sum_of_squares(16) == 1;

数论,数论


要用最短的时间解这道题,首先要知道一个定理,

拉格朗日四平方和定理:任意一个正整数都可以表示为不超过 4 个整数的平方和,也就是说本题的答案只有 1, 2, 3, 4 四种;

然后再用一个引理进行剪枝:4m(8k+7) 不能表示为 3 个平方数之和,那就是 4 咯,而且这还是所有的 4;

最后用 O(sqrt(n)) 的时间搜一遍 n = a2 + b2 就可以了(你也可以搜三个数的平方和,时间不会差太多)。

参考代码:

#include <cmath>
int sum_of_squares(int n) {
  while (n % 4 == 0) n /= 4; 
  if (n % 8 == 7) return 4;
  for (int a = 0; a * a < n; ++a) {
      int b = std::sqrt(n - a * a);
      if (a * a + b * b == n)
          return a ? 2 : 1;
  }
  return 3;
}