CF-1079-D. Another Problem about Beautiful Pairs

题目大意

在数组 $a$ 中，如果满足以下条件，我们称索引对 $i$, $j$ 为美丽的：

• $a_{i} \cdot a_{j} = j - i$。

统计数组 $a$ 中美丽对的数量。

思路讲解

使用比较聪明的暴力去枚举这个点，对呀。去枚枚举 X 和 Y 那么枚举 X Y 其实它是 N log N 的，实际上是。这应该也是一个经典结论了，可以使用调和级数证明，应该是。枚举 X 和 Y 以后呢，实际上就非常简单了。就是因为我们已经枚举出来，枚举出来以后，我们只需要验证一下这个数组当中有没有这样子的 X 和 Y 。我们可以选择去遍历 X 所有的位置，然后遍历到 X 位置 以后我们直接去检验应该有 Y 的那个地方是不是一个 Y 如果是 Y 的话，我们就给这个答案加一。

void Solve() {
    ll N;
    cin >> N;
    vector<ll> A(N+2);
    for (int i=1;i<=N;++i) {
        cin>>A[i];
    }
    vector<vector<ll>> val_pos_mtx(N+2);
    for (int i=1;i<=N;++i) {
        if (A[i]<=N) {
            val_pos_mtx[A[i]].push_back(i);
        }
    }
    ll ans=0;
    for (ll x=1;x<=N;++x) {
        if (val_pos_mtx[x].empty()) continue;
        for (ll y=1;y<=N/x;++y) {
            if (val_pos_mtx[y].empty()) continue;
            ll mul=x*y;
            for (auto i:val_pos_mtx[x]) {
                ll j=i+mul;
                if (j<=N && A[j]==y) {
                    ++ans;
                }
            }
        }
    }
    cout<<ans<<"\n";
}

AC代码

AC

https://codeforces.com/contest/2197/submission/362477014

源代码

/**
 * Problem: D. Another Problem about Beautiful Pairs
 * Contest: Codeforces Round 1079 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2197/problem/D
 * Created: 2026-02-11 23:14:12
 * Author: Gospel_rock
 *
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define debug3d(a)                                         \
cerr << #a << " = [\n";                                \
for (int i = 0; i < (int)(a).size(); i++)              \
{                                                      \
cerr << "  [\n";                                   \
for (int j = 0; j < (int)(a[i]).size(); j++)       \
{                                                  \
cerr << "    [";                               \
for (int k = 0; k < (int)(a[i][j]).size(); k++) \
cerr << (k ? ", " : "") << a[i][j][k];     \
cerr << "]\n";                                 \
}                                                  \
cerr << "  ]\n";                                   \
}                                                      \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */

void Solve() {
    ll N;
    cin >> N;
    vector<ll> A(N+2);
    for (int i=1;i<=N;++i) {
        cin>>A[i];
    }
    vector<vector<ll>> val_pos_mtx(N+2);
    for (int i=1;i<=N;++i) {
        if (A[i]<=N) {
            val_pos_mtx[A[i]].push_back(i);
        }
    }
    ll ans=0;
    for (ll x=1;x<=N;++x) {
        if (val_pos_mtx[x].empty()) continue;
        for (ll y=1;y<=N/x;++y) {
            if (val_pos_mtx[y].empty()) continue;
            ll mul=x*y;
            for (auto i:val_pos_mtx[x]) {
                ll j=i+mul;
                if (j<=N && A[j]==y) {
                    ++ans;
                }
            }
        }
    }
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*


*/

心路历程（WA，TLE，MLE……）