给一个整数,表示成n个整数的平方和,n最小,求n。
10017 = 100^2 + 4^2 + 1 --> n = 3
这道题的快速解法要牵扯到数学定理了。
Lagrange's four-square theorem
Every natural number can be represented as the sum of four integer squares.
Legendre's three-square theorem
Let m, n be integers equal to or greater than 0. If N = 4m(8n+7), then N is NOT expressible as the sum of three squares of integers.
Example:
1584 = 42(8(12)+3) thus not in the form 4m(8n+7), so it can be expressed as the sum of 3 squares.
960 = 43(8(1)+7). Because it is of the form 4m(8n+7), it cannot be expressed as the sum of 3 squares.
Interesting Note:
For the equation N = 4m(8n+7), the (8n+7) part is equivalent to 7 mod 8. This stems from the fact that every square of a number is either 0,1, or 4 mod 8. Since this holds true for the squares of numbers, no integer congruent to 7 mod 8 can be represented as the sum of three squares. Therefore, we must have some numbers that need to be represented by the sum of four 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;
int numOfSquares(int n) { if(n < 0) return 0; if(n <= 1) return 1; vector<int> f(n+1, 4); f[0] = f[1] = 1; for(int i=2; i<=n; i++) { int rt = (int)sqrt(i); if(rt*rt == i) { f[i] = 1; continue; } for(int j=1; j<=rt; j++) { f[i] = min(f[i], f[i-j*j]+1); if(f[i] == 2) break; // optional } } return f[n]; } int numOfSquares2(int n) { if(n < 0) return 0; unordered_set<int> set; int rt = (int)sqrt(n); if(rt*rt == n) return 1; for(int i=1; i<=rt; i++) { set.insert(i*i); } for(int i=1; i<=rt; i++) { if(set.count(n-i*i)) return 2; } while(n % 4 == 0) n /= 4; if(n % 8 != 7) return 3; return 4; }
Reference:
http://www.1point3acres.com/bbs/thread-17806-1-1.html
http://math453spring2009.wikidot.com/lecture-32:integers-as-sums-of-squares
相关推荐
leetcode伪代码find-n-unique-integers-sum-up-to-zero 题目解读: 题目来源: 原文: Given an integer n, return any array containing n unique integers such that they add up to 0. 解读: 给定一个正整数n, ...
Laravel开发-laravel-validate-mysql-integers 确保值在有效的MySQL整数范围内的验证规则。
SumZero ( int n ) { var arr = new int [ n ]; int j = 0 ; int x = 1 ; for ( int i = 0 ; i < n / 2 ; i ++ ) { arr [ j ++ ] = x ; arr [ j ++ ] = - 1 * x ; x ++ ; } if ( n % 2 == 1 ) arr [ j ] = 0 ; ...
C Hello, World! Program
leetcode 不会二和整数数组 给定一个整数数组,返回两个数字的索引,使它们相加为特定目标。 您可以假设每个输入都只有一个解决方案,并且您不能两次使用相同的元素。 例子: Given nums = ...但是,我们可以很快推断出...
R code. There are two functions: evenProduct(num) gives product of all even positive integers less then or equal to num evenSum(num) gives sum of all even positive integers less then or equal to num
支持手势滑动的顶部菜单导航源码, 每个菜单会有背景图片的滑动效果
假设用户通过具有适当iam权限的aws-runas登录,或者应用程序承担具有适当权限的角色。 请参考Dockerfile.Production 日期 2021年3月7日 部署的应用程序的位置 不适用 所花费的时间 约10个小时(包括研究在内) 假设...
INTAL--任意长度的整数 INTAL是一个C库,它为C语言提供BigIntegers支持。 C中的无符号长整数的最大限制为18446744073709551615(20位数字)。 虽然C ++ / java之类的语言支持BigIntegers类(100位数字)。...
使用django的两个整数之间的所有素数 要运行此目录,请使用以下命令行:-$ python manage.py runserver primeno是主目录prime是应用程序目录 ... 我们已经将这些详细信息保存在datbase(sqlite3)中。...
integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same ...
interview-algorithm 记录前端面试算法题目详解 目录 Lost Three Nums 随机从一组数组(数组内的数据为从1到n,且n为正整数)里,删除三个数,要求找到丢失的三个数,且运行较快。采用map记录仍在数组内的数据,再...
squares of integers program
A tighter bound for the character sum of primitive sequences over residue rings modulo square-free odd integers
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return ...
An Exposition of the Eisenstein Integers An Exposition of the Eisenstein Integers
Given a specified total t and a list of n integers, find all distinct sums using numbers from the list that add up to t. For example, if t=4, n=6, and the list is [4,3,2,2,1,1], then there are four ...
sortIntegers ( a , b ) { return a - b ; } // Greatest product is either (min1 * min2 * max1 || max1 * max2 * max3) function computeProduct ( unsorted ) { var sortedArray = unsorted . sort ( sort...
Column 12: Generate a sorted list of random integers sortedrand.cpp -- Several algorithms for the task. Column 13: Set representations for the problem in Column 12 sets.cpp -- Several data ...