两两相乘求和

article/2025/8/16 0:11:02

给定 n 个整数 a_1, a_2, · · · , a_na1,a2,⋅⋅⋅,an ，求它们两两相乘再相加的和，即：

$S=a_{1} \cdot a_{2}+a_{1} \cdot a_{3}+\cdots+a_{1} \cdot a_{n}+a_{2} \cdot a_{3}+\cdots+a_{n-2} \cdot a_{n-1}+a_{n-2} \cdot a_{n}+a_{n-1} \cdot a_{n}$

输入格式

输入的第一行包含一个整数 n。

第二行包含 n 个整数 $a_1,a_2,....,a_n$ 。

输出格式

输出一个整数 S，表示所求的和。请使用合适的数据类型进行运算。

#include <iostream>
using namespace std;
int a[200003] = { 0 };
int main()
{// 请在此输入您的代码long long Y = 0;//和int N = 0;scanf("%d", &N);int n = N;int i = 0;while (n--) {scanf("%d", &a[i]);i++;}for (int j = 0; j < N-1; j++) {for (int k = j+1; k < N; k++) {Y=Y+(a[j] * a[k]);}}printf("%lld", Y);return 0;
}

N很大的时候，会超时。

提取公因式可以发现原计算式可以化为
S=a1·a2+(a1+a2)·a3+(a1+a2+a3)·a4+···+(a1+a2+a3+···+an-2+an-1)·an
所以我们只要维护一个当前读取进来的不包括当前数字的前缀和然后每次与当前的数字相乘然后累加即可，就可以得到上面的代码，这种方法只需要循环一边即可时间复杂度为O(n)。

参考来源：(59条消息) 蓝桥杯真题求和给定 n 个整数 a1· a2, · · · , an，求它们两两相乘再相加的和_七宫智音小天使的博客-CSDN博客

#include <bits/stdc++.h>
using namespace std;
int main() {long long n,temp,x,sum;cin >> n;x=0;sum=0;for (long long i = 0; i < n; i++) {scanf("%d", &temp);sum += x * temp;x += temp;}cout << sum;return 0;
}