F 签到

思路

这个求区间 GCD (LCM) 的方法让我耳目一新啊，原理和埃氏筛相似。先找到两个互素的元素，然后筛上去，时间复杂度 $O(mn)$。

for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (!a[i][j])
                for (int u = i, v = j; u <= n && v <= m; u += i, v += j)
                    a[u][v] = i * v;

后面直接单调队列即可。

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5e3 + 5;
int a[N][N], b[N][N];

int main() {
    int n, m, k;
    cin >> n >> m >> k;

    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (!a[i][j])
                for (int u = i, v = j; u <= n && v <= m; u += i, v += j)
                    a[u][v] = i * v;

    deque<int> que;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            while (!que.empty() && j - que.front() + 1 > k)         que.pop_front();
            while (!que.empty() && a[i][que.back()] <= a[i][j])     que.pop_back();
            que.push_back(j);
            b[j][i] = a[i][que.front()];
        }
        que.clear();
    }

    ll ans = 0;
    for (int j = k; j <= m; ++j) {
        for (int i = 1; i <= n; ++i) {
            while (!que.empty() && i - que.front() + 1 > k)         que.pop_front();
            while (!que.empty() && b[j][que.front()] <= b[j][i])    que.pop_back();
            que.push_back(i);
            if (i >= k)
                ans += b[j][que.front()];
        }
        que.clear();
    }
    cout << ans << endl;
    return 0;
}