给一个n*m的格点图,问其中有多少个矩形?
$ \sum_{x=1}^{nm} \sum_{ab=x} [a + b \leq n](n - a - b + 1)\sum_{cd=x} [c + d \leq m](m - c - bd + 1)$
#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef long long ll; #define rep(i, j, k) for (int i = int(j); i <= int(k); ++ i) const int N = 2507; LL f[N * N], g[N * N]; int main() { LL n, m; cin >> n >> m; n --; m --; rep(i, 1, n) rep(j, 1, n - i) if (i * j < N * N) f[i * j] += (LL)(n - i - j + 1); rep(i, 1, m) rep(j, 1, m - i) if (i * j < N * N) g[i * j] += (LL)(m - i - j + 1); LL ans = 0; rep(i, 1, N * N - 1) { // if (f[i] * g[i]) cout << i << '\n'; ans += f[i] * g[i]; } ans += (n * (n + 1) / 2) * (m * (m + 1) / 2); cout << ans << '\n'; }