Znzryb's Blog

Int 和 Long long 的循环变量类型性能基准测试

Posted on 2026-02-12 Edited on 2026-04-06

使用 int integer 作为循环变量类型和使用 long long 作为循环变量类型，这个速度几乎是一模一样的。所以之后可你可以这个，之后我们就用 long long 吧，避免这个溢出风险。

https://quick-bench.com/q/QWglJiYzyTVmjjHDhioI4S2UDOk

#include <benchmark/benchmark.h>
#include <cstdint>

constexpr int N = 100000000;

static void BM_loop_int(benchmark::State& state) {
    for (auto _ : state) {
        std::uint64_t acc = 0;
        for (int i = 0; i < N; ++i) {
            acc += (unsigned)i;
        }
        benchmark::DoNotOptimize(acc);
    }
}
BENCHMARK(BM_loop_int);

static void BM_loop_ll(benchmark::State& state) {
    for (auto _ : state) {
        std::uint64_t acc = 0;
        for (long long i = 0; i < (long long)N; ++i) {
            acc += (unsigned)i;
        }
        benchmark::DoNotOptimize(acc);
    }
}
BENCHMARK(BM_loop_ll);

The 2025 ICPC 德国 German Collegiate Programming Contest——F. Fair and Square

Posted on 2026-02-12 Edited on 2026-04-06

题目大意

题目背景
Felix 的生日派对上，一张 $H \times W$ 的矩形披萨被客人吃掉了一些部分，剩下的部分由若干 $1 \times 1$ 的正方形单元格组成。

题目描述
给出一个 $H \times W$ 的网格，其中字符 # 表示剩下的披萨块，. 表示已经被吃掉（空缺）的部分。
你需要将所有剩下的披萨块（#）划分成若干个边长为 $k$ 的正方形区域。
要求：

每个划分出的正方形必须完全由 # 组成。
所有 # 必须被恰好覆盖一次（不能重叠，不能遗漏）。
只能沿网格线切割。
划分出的所有正方形边长必须相等。

求满足上述条件的最大边长 $k$ 。

输入格式
第一行包含两个整数 $H$ 和 $W$ ( $1 \le H, W \le 2500$ )，表示网格的高度和宽度。
接下来 $H$ 行，每行包含一个长度为 $W$ 的字符串，由 # 和 . 组成。
保证输入中至少包含一个 #。

输出格式
输出一个整数，表示最大的可行边长 $k$ 。

样例 1

Input
4 7
####...
####.##
.######
.####..

Output
2

样例 1 解释
对于第一个样例，最大边长为 2。
剩下的披萨块可以被划分为 5 个 $2 \times 2$ 的正方形，其左上角坐标 $(r, c)$ 分别为： $(0,0), (0,2), (1,5), (2,1), (2,3)$ 。
所有 # 均被这 5 个正方形不重不漏地覆盖。

这道题说白了其实意思很简单，就是井号的地方代表就是披萨，然后你要把披萨切成正方形的，大小相同的块，问这些切出来的正方形块的最大边长是多少？

样例 2

Input
3 5
#####
#####
###..

Output
1

样例 3

Input
3 5
.##..
#####
##.##

Output
1

样例 4

Input
5 13
....###......
....###..###.
.######..###.
.###.....###.
.###.........

Output
3

思路讲解

首先呢我们还是要想到啊，就是我我们首先还是要想到一个算法，能够判定在此边长下能否切割出这样子的东西啊。

这个算法的时间复杂度就是 $O (H \times W)$ 就行，可以了。

这算法其实很简单，也不需要前缀和啊什么之类的。其实只需要一个贪心即可。就说白了，最上面的那个点，最上面最左边的那个点，或者你倒过来做最最左边最上面的那个点。你不放一个正方形在上面，就不以这个正方形，不放一个正方形在这里的话，没有正方形可以覆盖这个点，所以这里必须放一个正方形。就这个披萨点。必须放一个正方形。那么你放了这，放下去这个正正方形以后，你就判断一下这个正方形会不会和其他你放的正方形重叠，啊什么之类的就行了。说白了就是一个贪心。

auto check=[&](ll len) -> bool {
      ++tim;
      for (ll i=1;i<=N;++i) {
          for (ll j=1;j<=M;++j) {
              if (vis[i][j]>=tim) continue;
              if (maze[i][j]=='#') {
                  if (i+len-1>N) {
                      return false;
                  }
                  if (j+len-1>M) {
                      return false;
                  }
                  for (ll x=i;x<i+len;++x) {
                      for (ll y=j;y<j+len;++y) {
                          if (maze[x][y]!='#') {
                              return false;
                          }
                          if (vis[x][y]>=tim) {
                              return false;
                          }
                          vis[x][y]=tim;
                      }
                  }
              }
          }
      }
      return true;
  };

现在问题就来到什么呢？就是我不可能枚举2500次是吧？枚举2500次就超了。那我怎么样枚举的次数少一点？我其实就加一个非常简单的一个判定即可。它 cnt 的因数数量肯定是根号下 cnt，也就是数量级是2500。又因为 i 乘 i 才是才能组成 cnt 的一个因数，所以实际上 i 只有50的量级。

for (ll i=min(N,M);i>=2;--i) {
    if (cnt%(i*i)!=0) {
        continue;
    }
    if (check(i)) {
        cout<<i<<"\n";
        return;
    }
}
cout<<1<<"\n";

AC代码

AC
https://codeforces.com/gym/106129/submission/362620886

源代码

/**
 * Problem: F. Fair and Square
 * Contest: 2025
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106129/problem/F
 * Created: 2026-02-11 17:46:33
 * 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;

/*
 *
 */
//  minp[i] 存储的是i的最小素因数
// https://www.luogu.com.cn/record/221554377
vector<ll> minp,primes;
void sieve(ll n){
    minp.assign(n+5,0);
    // minp[1]=1;  // 加了这句话可能把 1 误判成素数，要小心
    for(int i=2;i<=n;++i){
        if(minp[i]==0){		// 是素数
            minp[i]=i;
            primes.push_back(i);
        }
        for(auto p:primes){
            if(i*p>n){	// 超范围了
                break;
            }
            minp[i*p]=p;
            // 为了保证每个合数都只被其【最小的】那个质因数标记一次 break
            // i * p_next = (p * k) * p_next 最小的应该是p
            if(p==minp[i]){
                break;
            }
        }
    }
}

void Solve() {
    ll N,M;
    cin >> N >> M;
    vector<vector<char>> maze(N+2,vector<char>(M+2));
    ll cnt=0;
    for (ll x=1;x<=N;++x) {
        for (ll y=1;y<=M;++y) {
            cin>>maze[x][y];
            if (maze[x][y]=='#') {
                ++cnt;
            }
        }
    }
    int tim=0;
    vector<vector<int>> vis(N+2,vector<int>(M+2));
    auto check=[&](ll len) -> bool {
        ++tim;
        for (ll i=1;i<=N;++i) {
            for (ll j=1;j<=M;++j) {
                if (vis[i][j]>=tim) continue;
                if (maze[i][j]=='#') {
                    if (i+len-1>N) {
                        return false;
                    }
                    if (j+len-1>M) {
                        return false;
                    }
                    for (ll x=i;x<i+len;++x) {
                        for (ll y=j;y<j+len;++y) {
                            if (maze[x][y]!='#') {
                                return false;
                            }
                            if (vis[x][y]>=tim) {
                                return false;
                            }
                            vis[x][y]=tim;
                        }
                    }
                }
            }
        }
        return true;
    };
    for (ll i=min(N,M);i>=2;--i) {
        if (cnt%(i*i)!=0) {
            continue;
        }
        if (check(i)) {
            cout<<i<<"\n";
            return;
        }
    }
    cout<<1<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif
    sieve(2600);
    // cin >> lT;
    // for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
AC
https://codeforces.com/gym/106129/submission/362620886

*/

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

https://qoj.ac/submission/2030500

出问题的代码

/**
 * Problem: F. Fair and Square
 * Contest: 2025
 * Judge: Codeforces
 * URL: https://codeforces.com/gym/106129/problem/F
 * Created: 2026-02-11 17:46:33
 * 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,M;
    cin >> N >> M;
    vector<vector<char>> maze(N+2,vector<char>(M+2));
    for (ll x=1;x<=N;++x) {
        for (ll y=1;y<=M;++y) {
            cin>>maze[x][y];
        }
    }
    int tim=0;
    vector<vector<int>> vis(N+2,vector<int>(M+2));
    auto check=[&](ll len) -> bool {
        ++tim;
        for (ll i=1;i<=N;++i) {
            for (ll j=1;j<=M;++j) {
                if (vis[i][j]>=tim) continue;
                if (maze[i][j]=='#') {
                    if (i+len-1>N) {
                        return false;
                    }
                    if (j+len-1>M) {
                        return false;
                    }
                    for (ll x=i;x<i+len;++x) {
                        for (ll y=j;y<j+len;++y) {
                            if (maze[x][y]!='#') {
                                return false;
                            }
                            if (vis[x][y]>=tim) {
                                return false;
                            }
                            vis[x][y]=tim;
                        }
                    }
                }
            }
        }
        return true;
    };
    ll ans=1;
    for (ll len=2;len*len<=max(N,M);++len) {
        if (check(len)) {
            ans*=len;
        }
    }
    ans=min(ans,min(N,M));
    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;
}

/*

*/

上面这个代码的问题是出在哪里呢？首先第一啊，就是这个因数啊，你直接乘起来，它去找这个最大，其实是不大对的。那么在 m 比较小的情况下，不如直接倒序遍历 m ，然后检验这个 m 的所有的素因数。是否全部都在我们可以凑出来的素因数集合之中。

不过后面我们发现更加大的问题，就是它这个道题目，它其实并不符合说有这个因数，然后我们乘，然后它就能够合在一起，即只要素因数合法，那么所凑出来的合数也合法，这其实是不对的，它们乘起来的合数是不一定合法的。其实很简单吧，就是边长为2和边长为3是没有反例的（即满足边长为2和满足边长为3，在不限制这个长度的情况下，应该是有满足边长为6的解决方案）。这个状况，让我们造成了一些错觉，以为说这个其实是可以乘的。但实际上不是这样子的。**满足边长为2，那一定满足边长为4吗？**一定满足边长为8吗？你看它这个2，它可以乘，它，但是它乘上去它就不一定对了。

CF-1079-B. Array and Permutation

Posted on 2026-02-11 Edited on 2026-04-06

题目大意

给定一个长度为 $n$ 的排列 $p$ 和一个长度为 $n$ 的数组 $a$ 。

你可以进行任意次操作，每次操作选择一个下标 $i$ （ $1 \le i < n$ ），然后执行以下两种之一：

把 $p_i$ 的值覆盖为 $p_{i+1}$ （即 $p_i := p_{i+1}$ ）
把 $p_{i+1}$ 的值覆盖为 $p_i$ （即 $p_{i+1} := p_i$ ）

也就是说，每次选两个相邻元素，把其中一个的值复制到另一个上。

判断是否能通过若干次操作，把排列 $p$ 变成数组 $a$ 。

样例解释：

第一组： $p = [1, 2, 3]$ ， $a = [1, 2, 2]$ 。选 $i = 2$ ，把 $p_2$ 的值复制到 $p_3$ ，得到 $[1, 2, 2]$ ，与 $a$ 相同，输出 YES。

第二组： $p = [3, 1, 2, 4]$ ， $a = [3, 4, 2, 2]$ ，无论如何操作都无法得到 $a$ ，输出 NO。

第三组： $p = [1, 3, 2, 5, 4]$ ， $a = [3, 3, 3, 5, 4]$ 。先选 $i = 1$ ，把 $p_2$ 的值复制到 $p_1$ ，得到 $[3, 3, 2, 5, 4]$ ；再选 $i = 2$ ，把 $p_2$ 的值复制到 $p_3$ ，得到 $[3, 3, 3, 5, 4]$ ，与 $a$ 相同，输出 YES。

思路讲解

使用类似于双指针的做法，判断这个 A 数组是去重以后是否是 P 数组 P 排列的子序列。具体来说，在实现当中，我们是使用 P 排列去对应 A 的这个数组，去对应 A 数组，就是你可以理解为我们用一个 PI 去消 AJ 去消 A 数组中的元素，那么这个 pi 当然是可以一直消一直消，可以消除连续的 aj 的元素，只要 aj 和 pi 相等，连续的相等就可以。但是 pi 一旦遇到了第一个和自己不相等的 aj 就会停下来。

void Solve() {
    ll N;
    cin >> N;
    vector<ll> P(N+2),A(N+2);
    for (int i=1;i<=N;++i) {
        cin>>P[i];
    }
    for (int i=1;i<=N;++i) {
        cin>>A[i];
    }
    ll bp=1;
    for (ll i=1;i<=N;++i) {
        bool isbreak=false;
        for (ll j=bp;j<=N;++j) {
            if (P[i]!=A[j]) {
                bp=j;
                isbreak=true;
                break;
            }
        }
        if (!isbreak) {
            bp=N+1;
        }
    }
    if (bp==N+1) {
        cout<<"YES\n";
    }else {
        cout<<"NO\n";
    }
}

AC代码

AC
https://codeforces.com/contest/2197/submission/362443575

源代码

/**
 * Problem: B. Array and Permutation
 * Contest: Codeforces Round 1079 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2197/problem/B#
 * Created: 2026-02-11 23:03:41
 * 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> P(N+2),A(N+2);
    for (int i=1;i<=N;++i) {
        cin>>P[i];
    }
    for (int i=1;i<=N;++i) {
        cin>>A[i];
    }
    ll bp=1;
    for (ll i=1;i<=N;++i) {
        bool isbreak=false;
        for (ll j=bp;j<=N;++j) {
            if (P[i]!=A[j]) {
                bp=j;
                isbreak=true;
                break;
            }
        }
        if (!isbreak) {
            bp=N+1;
        }
    }
    if (bp==N+1) {
        cout<<"YES\n";
    }else {
        cout<<"NO\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;
}

/*
AC
https://codeforces.com/contest/2197/submission/362443575


*/

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

CF-1079-D. Another Problem about Beautiful Pairs

Posted on 2026-02-11 Edited on 2026-04-06

题目大意

在数组 $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代码

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……）

CF-1079-C. Game with a Fraction

Posted on 2026-02-11 Edited on 2026-04-06

题目大意

题目： C. 带有分数的游戏

题意：
Alice 和 Bob 玩一个游戏，初始有两个整数 $p$ 和 $q$ 。Alice 先手，两人轮流进行操作。
每回合玩家可以执行以下操作之一：

将 $p$ 减少 1（需满足 $p > 0$ ）。
将 $q$ 减少 1（需满足 $q > 1$ ）。

游戏在 $p=0$ 且 $q=1$ 时结束。

胜负判定：

Bob 获胜：如果在游戏过程中的任意时刻（包括初始状态），分数 $\frac{p}{q}$ 的值等于 $\frac{2}{3}$ 。
Alice 获胜：如果游戏结束时 Bob 仍未获胜。
假设双方都采取最优策略，判断谁是赢家。

样例解释：

输入 4 6：初始 $\frac{4}{6} = \frac{2}{3}$ ，Bob 立即获胜。
输入 10 14：双方博弈过程中，可能会到达状态 $p=8, q=12$ ，此时 $\frac{8}{12} = \frac{2}{3}$ ，Bob 获胜。
输入 15 15：Alice 存在必胜策略，使得游戏过程中分数永远不等于 $\frac{2}{3}$ ，最终 Alice 获胜。

思路讲解

不难推出，3P 小于2Q 时无答案。（糖水不等式就是把，这个糖水不等式就是把糖从溶液里面抠出来，溶液质量和糖的质量它都会减。按照实际生活常识，我们知道此时溶液浓度肯定是下降的，因为你少加点糖，那溶液浓度总归是减的呀，不会增呀，对吧？）

AI 讲解

你提到的糖水不等式其实两个方向都能用，而且恰好就是切入点。

糖水不等式回顾

如果 $\frac{p}{q} < 1$ （即 $p < q$ ），那么分子分母同时减去相同正数后，分数变小：

\frac{p - 1}{q - 1} < \frac{p}{q} \quad (\text{当}\ p < q)

如果 $\frac{p}{q} \geq 1$ （即 $p \geq q$ ），则反过来，分数变大（或不变）。

镜像策略 = 分子分母同时减 1

Bob 的镜像策略效果是：每一轮 $p$ 和 $q$ 各减 1，Alice 无法干预。那每一轮分数从 $\frac{p}{q}$ 变成 $\frac{p-1}{q-1}$ 。

$p/q > 2/3$ 时的两种情况

情况一： $\frac{2}{3} < \frac{p}{q} < 1$ （即 $p < q$ ）
分数在 $\frac{2}{3}$ 和 $1$ 之间。由糖水不等式，每轮分子分母同减 1 后分数变小，朝着 $\frac{2}{3}$ 靠近。而 $v = 3p - 2q$ 每轮恰好减 1（整数），所以不会"跳过" $\frac{2}{3}$ ，一定会精确命中 $v = 0$ 。Bob 赢。
情况二： $\frac{p}{q} \geq 1$ （即 $p \geq q$ ）
分数 $\geq 1$ 。由糖水不等式，分子分母同减 1 后分数变大（远离 $\frac{2}{3}$ ）。而且 $q$ 的余量不够—— $q$ 会先降到 1，此后只能减 $p$ ， $v$ 每步变化 $-3$ ，从 $v \equiv 1 \pmod{3}$ 开始逐步减，永远跳过 $0$ 。Alice 赢。

总结

条件	糖水不等式效果	结果
$\frac{p}{q} = \frac{2}{3}$	已经命中	Bob 赢
$\frac{p}{q} < \frac{2}{3}$	分数远离 $\frac{2}{3}$ （变更小）	Alice 赢
$\frac{2}{3} < \frac{p}{q} < 1$	分数靠近 $\frac{2}{3}$ （变小）	Bob 赢
$\frac{p}{q} \geq 1$	分数远离 $\frac{2}{3}$ （变大）	Alice 赢
分界线就是 $\frac{p}{q} = 1$ ，即 $p = q$ 。
所以判定条件只有一句话：Bob 赢当且仅当 $3p \geq 2q$ 且 $p < q$ 。糖水不等式是两个方向上统一的判据。

AI 讲解 2

好问题。糖水不等式只告诉我们方向（变小），不保证精确命中 $\frac{2}{3}$ 。真正的保证来自 $v = 3p - 2q$ 这个量。

为什么一定能精确命中

镜像策略下，每轮 $p$ 和 $q$ 各减 1，所以：

v' = 3(p-1) - 2(q-1) = 3p - 2q - 1 = v - 1

$v$ 是整数，每轮恰好减 1。
起点 $v_0 = 3p - 2q > 0$ （正整数），每轮减 1：

v_0,\quad v_0 - 1,\quad v_0 - 2,\quad \ldots,\quad 2,\quad 1,\quad 0

它是逐个整数递减的，不可能跳过 0。所以 $v = 0$ 一定会被经过。

和糖水不等式的关系

糖水不等式告诉你的是分数 $\frac{p}{q}$ 在变小，但分数是有理数，变小不代表能精确等于某个值（比如你可能担心 $0.672, 0.669, 0.665, \ldots$ 这样跳过了 $\frac{2}{3} = 0.6\overline{6}$ ）。
但 $v = 3p - 2q$ 是整数世界的东西。 $\frac{p}{q} = \frac{2}{3}$ 等价于 $v = 0$ 。每轮 $v$ 减 1，从正整数出发，必然经过 0。这就是精确命中的保证。

还要确认的一件事

$v$ 从 $v_0$ 减到 $0$ 需要 $v_0$ 轮，即 $2v_0$ 步。游戏总共有 $p + q - 1$ 步，所以需要：

2v_0 \leq p + q - 1

代入 $v_0 = 3p - 2q$ ：

2(3p - 2q) \leq p + q - 1 \iff 5p \leq 5q - 1 \iff p < q

这就是为什么 $p < q$ 是必要且充分的——它保证游戏在 $v$ 到达 $0$ 之前不会提前结束。
所以结论很清晰： $v$ 每轮整数减 1，不会跳过； $p < q$ 保证游戏撑得到那一轮。两个条件合在一起， $v = 0$ 一定会被命中。

那么 P 除以 Q 大于2/3是比较棘手的这个情况。然后我们又进行了一下分类讨论，然后说明了 P 除以 Q 大于等于一的时候，一定是没有解的。这是根据糖水不等式，其实就是颠倒个个嘛，就是颠倒个，就是水和糖不一样了，那么这个结果也也是自然是不一样的。然后是 p 除以 q 大于2/3小于一的时候，那么就是这个时候是 Bob 一定是赢的，因为我们写在这个图片里面了，它一定有一个合法解。

AC代码

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

源代码

/**
 * Problem: C. Game with a Fraction
 * Contest: Codeforces Round 1079 (Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2197/problem/C
 * Created: 2026-02-11 22:58:39
 * 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 p,q;
    cin >> p >> q;
    __int128 a = (__int128)3 * p;
    __int128 b = (__int128)2 * q;
    __int128 c = (__int128)3 * q;

    if (b <= a && a < c) cout << "Bob\n";
    else cout << "Alice\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;
}

/*



*/

题目大意

思路讲解

AC代码

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

题目大意

思路讲解

AC代码

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

题目大意

思路讲解

AC代码

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

题目大意

思路讲解

糖水不等式回顾

镜像策略 = 分子分母同时减 1

p/q>2/3p/q > 2/3p/q>2/3 时的两种情况

总结

为什么一定能精确命中

和糖水不等式的关系

还要确认的一件事

AC代码

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

$p/q > 2/3$ 时的两种情况