集合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\time j}$$
问题陈述
给定一个数字n。在范围（1，n）内，包括n和1，找到成对乘积的总和。
示例示例1
Input: n = 4
Output: 65
Explanation
的中文翻译为：解释
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
Explanation
的中文翻译为：解释
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
方法一：暴力破解方法
解决这个问题的蛮力解法是使用两个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++实现
在以下程序中，我们找到所有可能的配对，然后找到乘积的和。
#includeusing 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)
方法二
以n = 4为例，
I = 1*1 + 1*2 + 1*3 + 1*4 + 2*2 + 2*3 + 2*4 + 3*3 + 3*4 + 4*4
在简化上述内容时，
I = 1*1 + (1+2)*2 + (1+2+3)*3 + (1+2+3+4)*4
取prefix_sum[1] = 1，
前缀总和[2] = 1+2，
前缀总和[3] = 1+2+3，
前缀总和[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++实现
在下面的程序中，我们找到每次迭代的和，即前缀和，并乘以迭代次数，然后在每一步中加到最终和中。
#includeusing 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内的数字的两两乘积之和的求解，我们可以采用上述两种方法之一，其中第一种方法是暴力法，时间复杂度为O(n^2)，第二种方法是使用前缀和来计算两两乘积之和的优化方法，时间复杂度为O(n)。
