数学！！！简单 大大降低时间复杂度

解题思路：普通暴力嵌套两个循环可以算出来 但是时间超限 那就不得不改变算法了。

给定一组数 a1,a2,…,an，我们要求的是它们两两相乘的和，即：S=a1a2+a1a3+⋯+an−1an

为了简化计算,设：所有数的和sum 和所有数的平方和 sq：

sum=a1+a2+⋯+an

sq=a12+a22+⋯+an2

如果我们计算sum2，即所有数的和的平方，我们实际上计算了：sum^2=(a1+a2+⋯+an)^2=a1^2+a2^2+⋯+an^2+2(a1a2+a1a3+⋯+an−1an)=sq+2S

所以得出公式 S = （sum^2-sq)/2;

注意事项:

参考代码:

#include <iostream>

#include <vector>

#include <cstdio>

using namespace std;

int main()

{

    int n;

    scanf("%d",&n);

    vector<int> v(n);

    long long int S = 0,sum = 0,sq = 0;

    for(int i = 0;i<n;i++)

    {

        scanf("%d",&v[i]);

        sum += v[i];

        sq += (long long)v[i] * v[i];

    }

    S = (sum * sum - sq) / 2;

    printf("%lld\n",S);

    return 0;
}