P8772 [蓝桥杯 2022 省 A] 求和

题目描述

给定 𝑛 个整数 𝑎1,𝑎2,⋯ ,𝑎𝑛 求它们两两相乘再相加的和，即

𝑆=𝑎1⋅𝑎2+𝑎1⋅𝑎3+⋯+𝑎1⋅𝑎𝑛+𝑎2⋅𝑎3+⋯+𝑎𝑛−2⋅𝑎𝑛−1+𝑎𝑛−2⋅𝑎𝑛+𝑎𝑛−1⋅𝑎𝑛

输入格式

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

第二行包含 n 个整数 a1​,a2​,⋯an​ 。

输出格式

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

输入输出样例

输入 #1复制

4
1 3 6 9

输出 #1复制

117

---

#include<stdio.h>int main(){int n;long long sum=0,sum_of_squares=0,result=0;
scanf("%d",&n);
int a[n];
for(int i=0;i<n;i++){scanf("%d",&a[i]);sum+=a[i];sum_of_squares+=a[i]*a[i];}
result=(sum*sum-sum_of_squares)/2;
printf("%lld",result);
return 0;
}

这题主要是难在时间复杂度，如果简单的用两重循环那么一定会超时

这题实际考的是数学，就是比较难的思维推理

sum*sum包括所有乘积的和要减去i和j相同时的，因为ai*aj=aj*ai，所以要除以2