对于给定的任何无符号整数n，求∑（i*j）式中（1<=i<=n）和（i<=j<=n）。 例如：
null
Input : n = 3Output : 25We get the sum as following. Note thatfirst term i varies from 1 to 3 and secondterm values from value of first term to n.1*1 + 1*2 + 1*3 + 2*2 + 2*3 + 3*3 = 25Input : 5Output : 140
方法1（简单） 我们运行两个循环并计算所需的和。
C++
// Simple CPP program to find sum // of given series. #include <bits/stdc++.h> using namespace std; long long int findSum( int n) { long long int sum = 0; for ( int i=1; i<=n; i++) for ( int j=i; j<=n; j++) sum = sum + i*j; return sum; } int main() { int n = 5; cout << findSum(n); return 0; } |
JAVA
// Simple Java program to find sum // of given series. class GFG { static int findSum( int n) { int sum = 0 ; for ( int i= 1 ; i<=n; i++) for ( int j=i; j<=n; j++) sum = sum + i*j; return sum; } // Driver code public static void main(String[] args) { int n = 5 ; System.out.println(findSum(n)); } } // This code is contributed by Smitha Dinesh Semwal. |
Python3
# Simple Python3 program to # find sum of given series. def findSum(n) : sm = 0 for i in range ( 1 , n + 1 ) : for j in range (i, n + 1 ) : sm = sm + i * j return sm # Driver Code n = 5 print (findSum(n)) # This code is contributed by Nikita Tiwari. |
C#
// Simple C# program to find sum // of given series. class GFG { static int findSum( int n) { int sum = 0; for ( int i=1; i<=n; i++) for ( int j=i; j<=n; j++) sum = sum + i*j; return sum; } // Driver code public static void Main() { int n = 5; System.Console.WriteLine(findSum(n)); } } // This code is contributed by mits. |
PHP
<?php // Simple PHP program to find sum // of given series. function findSum( $n ) { $sum = 0; for ( $i = 1; $i <= $n ; $i ++) for ( $j = $i ; $j <= $n ; $j ++) $sum = $sum + $i * $j ; return $sum ; } // Driver Code $n = 5; echo findSum( $n ); // This code is contributed by mits ?> |
Javascript
<script> // Simple JavaScript program to find sum // of given series. function findSum(n) { let sum = 0; for (let i=1; i<=n; i++) for (let j=i; j<=n; j++) sum = sum + i*j; return sum; } // Driver Code let n = 5; document.write(findSum(n)); </script> |
输出：
140
时间复杂性： O（n^2）。 方法2（更好） 我们可以在给定的问题中观察到以下情况。 1乘以从1到n的所有数字。 2乘以从2到n的所有数字。 ……………………………………… ……………………………………… i乘以从i到n的所有数字。 我们计算前n个自然数的和，这是我们的第一项。对于剩余项，我们将i乘以从i到n的数字之和。我们通过在每次迭代中从初始和中减去i来跟踪这个和。
C++
// Efficient CPP program to find sum // of given series. #include <bits/stdc++.h> using namespace std; long long int findSum( int n) { long long int multiTerms = n * (n + 1) / 2; // Sum of multiples of 1 is 1 * (1 + 2 + ..) long long int sum = multiTerms; // Adding sum of multiples of numbers other // than 1, starting from 2. for ( int i=2; i<=n; i++) { // Subtract previous number // from current multiple. multiTerms = multiTerms - (i - 1); // For example, for 2, we get sum // as (2 + 3 + 4 + ....) * 2 sum = sum + multiTerms * i; } return sum; } // Driver code int main() { int n = 5; cout << findSum(n); return 0; } |
JAVA
// Efficient Java program to find sum // of given series. class GFG { static int findSum( int n) { int multiTerms = n * (n + 1 ) / 2 ; // Sum of multiples of 1 is 1 * (1 + 2 + ..) int sum = multiTerms; // Adding sum of multiples of numbers other // than 1, starting from 2. for ( int i = 2 ; i <= n; i++) { // Subtract previous number // from current multiple. multiTerms = multiTerms - (i - 1 ); // For example, for 2, we get sum // as (2 + 3 + 4 + ....) * 2 sum = sum + multiTerms*i; } return sum; } // Driver code public static void main(String[] args) { int n = 5 ; System.out.println(findSum(n)); } } // This code is contributed by Smitha Dinesh Semwal. |
Python3
# Efficient Python3 program # to find sum of given series. def findSum(n) : multiTerms = n * (n + 1 ) / / 2 # Sum of multiples of 1 is 1 * (1 + 2 + ..) sm = multiTerms # Adding sum of multiples of numbers # other than 1, starting from 2. for i in range ( 2 , n + 1 ) : # Subtract previous number # from current multiple. multiTerms = multiTerms - (i - 1 ) # For example, for 2, we get sum # as (2 + 3 + 4 + ....) * 2 sm = sm + multiTerms * i return sm # Driver code n = 5 print (findSum(n)) # This code is contributed by Nikita Tiwari. |
C#
// C# program to find sum // of given series. using System; class GFG { static int findSum( int n) { int multiTerms = n * (n + 1) / 2; // Sum of multiples of 1 is 1 * (1 + 2 + ..) int sum = multiTerms; // Adding sum of multiples of numbers other // than 1, starting from 2. for ( int i = 2; i <= n; i++) { // Subtract previous number // from current multiple. multiTerms = multiTerms - (i - 1); // For example, for 2, we get sum // as (2 + 3 + 4 + ....) * 2 sum = sum + multiTerms*i; } return sum; } // Driver code public static void Main() { int n = 5; Console.WriteLine(findSum(n)); } } // This code is contributed by Mukul Singh. |
PHP
<?php // Efficient PHP program to find sum // of given series. function findSum( $n ) { $multiTerms = (int)( $n * ( $n + 1) / 2); // Sum of multiples of 1 is 1 * (1 + 2 + ..) $sum = $multiTerms ; // Adding sum of multiples of numbers other // than 1, starting from 2. for ( $i =2; $i <= $n ; $i ++) { // Subtract previous number // from current multiple. $multiTerms = $multiTerms - ( $i - 1); // For example, for 2, we get sum // as (2 + 3 + 4 + ....) * 2 $sum = $sum + $multiTerms * $i ; } return $sum ; } // Driver code $n = 5; echo findSum( $n ); //This code is contributed by mits ?> |
Javascript
<script> // Javascript program to find // sum of given series. function findSum(n) { let multiTerms = n * (n + 1) / 2; // Sum of multiples of 1 is 1 * (1 + 2 + ..) let sum = multiTerms; // Adding sum of multiples // of numbers other // than 1, starting from 2. for (let i = 2; i <= n; i++) { // Subtract previous number // from current multiple. multiTerms = multiTerms - (i - 1); // For example, for 2, we get sum // as (2 + 3 + 4 + ....) * 2 sum = sum + multiTerms*i; } return sum; } let n = 5; document.write(findSum(n)); </script> |
输出：
140
时间复杂性： O（n）。 方法3（高效） 整个计算可以在O（1）时间内完成，因为求和有一个封闭形式的表达式。让i和j从1运行到n。我们要计算S=总和（i*j）总i和j，这样i<=j，否则我们会有重复项，比如2*3+…+3*2；另一方面，i=j是可以的，这给了我们2*2+…这都是由问题规范决定的。（如果我的符号有点奇怪，我很抱歉。） 现在，在和S中有两种类型的项：i=j的项（平方，表示为S1）和i=j的项，但其值是相同的，通过对称性：2*S2=（和i）^2–和（和i^2）。注意，2*S2=S3–S1，因为后者的和只是S1；前一个和（表示为S3）在这里是新的，但它也有一个封闭形式的解决方案。我们现在可以完全消除混合项：S=S1+S2=（S1+S3）/2。 由于和（i）=n*（n+1）/2，我们得到S3=n*n*（n+1）*（n+1）/4；同样，对于平方和：S1=n*（2*n+1）*（n+1）/6。最后一个表达式简化为： S=n*（n+1）*（n+2）*（3*n+1）/24。（作为练习，你可能想证明分子确实可以被24整除。）
C++
// Efficient CPP program to find sum // of given series. #include <bits/stdc++.h> using namespace std; long long int findSum( int n) { return n*(n+1)*(n+2)*(3*n+1)/24; } // Driver code int main() { int n = 5; cout << findSum(n); return 0; } |
JAVA
// Efficient Java program to find sum // of given series. class GFG { static int findSum( int n) { return n * (n + 1 ) * (n + 2 ) * ( 3 * n + 1 ) / 24 ; } // Driver code public static void main(String[] args) { int n = 5 ; System.out.println(findSum(n)); } } // This code is contributed by Smitha Dinesh Semwal. |
Python3
# Efficient Python3 program to find # sum of given series. def findSum(n): return n * (n + 1 ) * (n + 2 ) * ( 3 * n + 1 ) / 24 # Driver code n = 5 print ( int (findSum(n))) # This code is contributed by Smitha Dinesh Semwal. |
C#
// Efficient C# program // to find sum of given // series. using System; class GFG { static int findSum( int n) { return n * (n + 1) * (n + 2) * (3 * n + 1) / 24; } // Driver code static public void Main () { int n = 5; Console.WriteLine(findSum(n)); } } // This code is contributed // by ajit. |
PHP
<?php // Efficient PHP // program to find sum // of given series. function findSum( $n ) { return $n * ( $n + 1) * ( $n + 2) * (3 * $n + 1) / 24; } // Driver code $n = 5; echo findSum( $n ); // This code is contributed // by akt_mit ?> |
Javascript
<script> // Efficient Javascript program // to find sum of given // series. function findSum(n) { return n * (n + 1) * (n + 2) * (3 * n + 1) / 24; } let n = 5; document.write(findSum(n)); </script> |
输出：
140
时间复杂性： O（1）。 感谢diprey1提出了这个有效的解决方案。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
