集合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{displaystylesumlimits_{i=1,j=i}^{ileq n,jleq n}:(i,j)=itime 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++实现
在以下程序中,我们找到所有可能的配对,然后找到乘积的和。
#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)
方法二
以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++实现
在下面的程序中,我们找到每次迭代的和,即前缀和,并乘以迭代次数,然后在每一步中加到最终和中。
#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内的数字的两两乘积之和的求解,我们可以采用上述两种方法之一,其中第一种方法是暴力法,时间复杂度为O(n^2),第二种方法是使用前缀和来计算两两乘积之和的优化方法,时间复杂度为O(n)。
以上是两两乘积之和的详细内容。更多信息请关注PHP中文网其他相关文章!

时隔四个月,ByteDanceResearch与北京大学物理学院陈基课题组又一合作工作登上国际顶级刊物NatureCommunications:论文《TowardsthegroundstateofmoleculesviadiffusionMonteCarloonneuralnetworks》将神经网络与扩散蒙特卡洛方法结合,大幅提升神经网络方法在量子化学相关任务上的计算精度、效率以及体系规模,成为最新SOTA。论文链接:https://www.nature.com

MySQL中如何使用SUM函数计算某个字段的总和在MySQL数据库中,SUM函数是一个非常有用的聚合函数,它可以用于计算某个字段的总和。本文将介绍如何在MySQL中使用SUM函数,并提供一些代码示例来帮助读者深入理解。首先,让我们看一个简单的示例。假设我们有一个名为"orders"的表,其中包含了顾客的订单信息。表结构如下:CREATETABLEorde

一种受欢迎的通用编程语言是Python。它被应用于各种行业,包括桌面应用程序、网页开发和机器学习。幸运的是,Python具有简单易懂的语法,适合初学者使用。在本文中,我们将使用Python来计算矩阵的右对角线之和。什么是矩阵?在数学中,我们使用一个矩形排列或矩阵,用于描述一个数学对象或其属性,它是一个包含数字、符号或表达式的矩形数组或表格,这些数字、符号或表达式按行和列排列。例如−234512367574因此,这是一个有3行4列的矩阵,表示为3*4矩阵。现在,矩阵中有两条对角线,即主对角线和次对

6 月 23 日,澳大利亚量子计算公司 SQC(Silicon Quantum Computing)宣布推出世界上第一个量子集成电路。这是一个包含经典计算机芯片上所有基本组件的电路,但体量是在量子尺度上。SQC 团队使用这种量子处理器准确地模拟了一个有机聚乙炔分子的量子态——最终证明了新量子系统建模技术的有效性。「这是一个重大突破,」SQC 创始人 Michelle Simmons 说道。由于原子之间可能存在大量相互作用,如今的经典计算机甚至难以模拟相对较小的分子。SQC 原子级电路技术的开发将

本文由Cristian Bodnar 和Fabrizio Frasca 合著,以 C. Bodnar 、F. Frasca 等人发表于2021 ICML《Weisfeiler and Lehman Go Topological: 信息传递简单网络》和2021 NeurIPS 《Weisfeiler and Lehman Go Cellular: CW 网络》论文为参考。本文仅是通过微分几何学和代数拓扑学的视角讨论图神经网络系列的部分内容。从计算机网络到大型强子对撞机中的粒子相互作用,图可以用来模

阿里云机器学习平台PAI与华东师范大学高明教授团队合作在SIGIR2022上发表了结构感知的稀疏注意力Transformer模型SASA,这是面向长代码序列的Transformer模型优化方法,致力于提升长代码场景下的效果和性能。由于self-attention模块的复杂度随序列长度呈次方增长,多数编程预训练语言模型(Programming-basedPretrainedLanguageModels,PPLM)采用序列截断的方式处理代码序列。SASA方法将self-attention的计算稀疏化

使用math.Log2函数计算指定数字的以2为底的对数在数学中,对数是一个重要的概念,它描述了一个数与另一个数(所谓的底)的指数关系。其中,以2为底的对数特别常见,并在计算机科学和信息技术领域中经常用到。在Python编程语言中,我们可以使用math库中的log2函数来计算一个数字的以2为底的对数。下面是一个简单的代码示例:importmathdef

使用Python的abs()函数计算数值的绝对值绝对值是一个数与零点的距离,无论这个数是正数还是负数,其绝对值都是非负数。在Python中,我们可以使用内置函数abs()来计算一个数的绝对值。本文将详细介绍abs()函数的使用方法,并给出一些代码示例。abs()函数的语法如下:abs(x)其中,x是需要计算绝对值的数值。下面是一些使用abs()函数的示例:示


热AI工具

Undresser.AI Undress
人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

AI Hentai Generator
免费生成ai无尽的。

热门文章

热工具

Dreamweaver CS6
视觉化网页开发工具

适用于 Eclipse 的 SAP NetWeaver 服务器适配器
将Eclipse与SAP NetWeaver应用服务器集成。

mPDF
mPDF是一个PHP库,可以从UTF-8编码的HTML生成PDF文件。原作者Ian Back编写mPDF以从他的网站上“即时”输出PDF文件,并处理不同的语言。与原始脚本如HTML2FPDF相比,它的速度较慢,并且在使用Unicode字体时生成的文件较大,但支持CSS样式等,并进行了大量增强。支持几乎所有语言,包括RTL(阿拉伯语和希伯来语)和CJK(中日韩)。支持嵌套的块级元素(如P、DIV),

PhpStorm Mac 版本
最新(2018.2.1 )专业的PHP集成开发工具

Dreamweaver Mac版
视觉化网页开发工具