Acwing 2559. 数正方形（点阵正方形数量）

题意：

在一个 N×N 的点阵上，取其中 4 个点恰好组成一个正方形的 4 个顶点，一共有多少种不同的取法？

由于结果可能非常大，你只需要输出模 1e9+7 的余数。

如上图所示的正方形都是合法的。

数据范围：n<=1e6

解法：

扩展问题：计算n*m的点阵正方形数量

结论：

$设r=min(n,m)$

$那么ans={\sum }_{i=1}^r{i}^3-(n+m){\sum }_{i=1}^r{i}^2+nm{\sum }_{i=1}^{r}i$

$复杂度O(r)，配合自然数前k项和公式可以O(1)求解$

$自然数前k项和公式：$this

由于本题n较小，可以直接O(n)求解了

code：

#include<bits/stdc++.h> using namespace std; #define ll long long const int mod=1e9+7; signed main(){ ll n;scanf("%lld",&n); ll ans=0; for(ll i=1;i<=n;i++){ ans=(ans+i*i*i)%mod; ans=(ans-n*2*i*i)%mod; ans=(ans+n*n*i)%mod; } ans=(ans%mod+mod)%mod; printf("%lld\n",ans); return 0; }

---