P8772 [蓝桥杯 2022 省 A] 求和 新解法（非前缀和）

· · 题解

看到大佬们的前缀和代码，本蒟蒻自愧不如 qwq。

本题也可以用 完全平方公式！！！

推荐使用 博客 食用！

咳咳，先从一个简单的例子入手：

在 1，2，3，4，5，6，7，8，9，10 这些正整数中每两个数相乘的乘积之和是多少？

我们都知道这十个数两两相乘的乘积有 C_{10}^2=45 个，有多项式：

\frac{(1+2+3+ \cdots +9+10)^2-(1^2+2^2+3^2+ \cdots +9^2+10^2)}{2}

为这十个数两两相乘的乘积之和。

先看一下下面的算式：

(1+2+3+ \cdots +9+10)^2

由完全平方公式展开后为：

(1^2+2^2+3^2+ \cdots +9^2+10^2)+2 \times (1 \times 2+1 \times 3+ \cdots 9 \times 10)

不难发现多项式 (1 \times 2+1 \times 3+ \cdots 9 \times 10) 正是要求的答案！

易得：

(1 \times 2+1 \times 3+ \cdots 9 \times 10)=\frac{(1+2+3+ \cdots +9+10)^2-(1^2+2^2+3^2+ \cdots +9^2+10^2)}{2}

那么本题的公式就是：

\frac{(a_1+a_2+a_3+ \cdots +a_{n-1}+a_n)^2-({a_1}^2+{a_2}^2+{a_3}^2+ \cdots +{a_n}^2)}{2}

最后送上代码！

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,x,mul=0,sum=0;
//mul:和的平方
//sum:平方的和
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x;
        sum+=(x*x);
        mul+=x;
    }
    cout<<(mul*mul-sum)/2;
    return 0;
}