成對乘積之和

---

集合 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;
}

輸出

Pairwise Product = 1155

結論

總之，為了找到範圍 1 到 n 內數字的成對乘積之和（包括 1 和 n），我們可以遵循上述兩種方法中的任何一種，其中第一種是暴力方法，時間複雜度為 O(n^2)，第二種方法是使用字首和計算成對乘積之和的最佳化方法，時間複雜度為 O(n)。