C++ 两两配对乘积之和

集合X={a, b, c}的两两配对乘积可以定义为所有可能集合对的乘积的和。集合的配对为Y={a * a, a * b, a * c, b * b, b * c, c * c}，其中乘积是可交换的。因此，集合X的两两配对乘积是集合Y的元素之和，即aa + ab + ac + bb + bc + cc。

在数学术语中，可能的配对乘积之和可以表示为：

$\mathrm{\displaystyle\sum\limits_{i=1,j=i}^{i\leq n,j\leq n}:(i,j)=i\times j}$

问题陈述

给定一个数字n。找到范围(1, n)内两两配对乘积的和，包括n和1。

示例1

Input: n = 4

Output: 65

说明

i的取值范围是1到4，j的取值范围是从i到4。

1*1 + 1*2 + 1*3 + 1*4 + 2*2 + 2*3 + 2*4 + 3*3 + 3*4 + 4*4 = 1 + 2 + 3 + 4 + 4 + 6 + 8 + 9 + 12 + 16 = 65

示例2

Input: n = 10

Output: 1705

解释

变量i的范围从1到10，变量j的范围从i到10。

1*1 + 1*2 + … + 1*10 + 2*2 + 2*3 + … + 2*10 + 3*3 + 3*4 + … + 3*10 + 4*4 + 4*5 + … 4*10 + 5*5 + 5*6 + … + 5*10 + 6*6 + 6*7 + … 6*10 + 7*7 + 7*8 + … 7*10 + 8*8 + 8*9 + 8*10 + 9*9 + 9*10 + 10*10 = 1705

方法1：暴力方法

解决这个问题的暴力方法是使用两个for循环，第一个循环迭代1到n，第二个循环迭代第一个数到n的所有可能的数对。

伪代码

procedure pairwiseProduct (n)
   sum = 0
   for i = 1 to n
      for j = i to n
         sum = sum + (i * j)
end procedure

示例：C++ 实现

在下面的程序中，我们找到所有可能的配对，然后找出乘积的总和。

#include <bits/stdc++.h>
using namespace std;

// Function to find pairwise product over the range 1 to n, 1 and n inclusive
unsigned long long pairwiseProduct(unsigned int n){
   unsigned long long sum = 0;

   // First number: 1 <= i <= n
   for (unsigned int i = 1; i <= n; i++){

      // Second number: i <= j <= n
      for (unsigned int j = i; j <= n; j++){
         sum += i * j;
      }
   }
   return sum;
}
int main(){
   unsigned long long n = 9;
   cout << "Pairwise Product = " << pairwiseProduct(n);
   return 0;
}

输出

Pairwise Product = 1155

时间复杂度-O(n^2)

空间复杂度-O(1)

方法2

以n = 4为例，

Sum = 1*1 + 1*2 + 1*3 + 1*4 + 2*2 + 2*3 + 2*4 + 3*3 + 3*4 + 4*4

简化上述表达式，

Sum = 1*1 + (1+2)*2 + (1+2+3)*3 + (1+2+3+4)*4

取prefix_sum[1]=1，

prefix_sum[2]=1+2，

prefix_sum[3]=1+2+3，

prefix_sum[2]=1+2，

伪代码

procedure pairwiseProduct (n)
   sum = 0
   prefixSum = 0
   for i = 1 to n
      prefixSum = prefixSum + 1
      sum = sum + i * prefixSum
end procedure

示例：C++实现

在下面的程序中，我们在每次迭代中计算前缀和，并根据迭代次数进行乘法运算并加到最终和中的每一步。

#include <bits/stdc++.h>
using namespace std;

// Function to find pairwise product over the range 1 to n, 1 and n inclusive
unsigned long long pairwiseProduct(unsigned int n){
   unsigned long long sum = 0;
   unsigned long long prefixSum = 0;
   for (unsigned int i = 1; i <= n; i++){
      prefixSum += i;
      sum += i * prefixSum;
   }
   return sum;
}
int main(){
   unsigned long long n = 9;
   cout << "Pairwise Product = " << pairwiseProduct(n);
   return 0;
}