Codeforces Round 886 (Div. 4) F. We Were Both Children （模拟，思维，*1300）

本文主要是介绍Codeforces Round 886 (Div. 4) F. We Were Both Children （模拟，思维，*1300），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

米哈伊和斯拉夫克正在观察一组 $n$ 只青蛙，编号从 $1$ 到 $n$ ，最初都位于 $0$ 点。青 $i$ 的跳跃长度为 $a_i$ 。

每秒，青蛙 $i$ 向前跳跃 $a_i$ 个单位。在任何青蛙开始跳跃之前，斯拉夫和米哈伊可以在一个坐标上放置一个陷阱，以便捕捉所有经过相应坐标的青蛙。

但是，孩子们不能离开家太远，所以他们只能在第一个 $n$ 点(即坐标在 $1$ 和 $n$ 之间的点)放置一个陷阱，孩子们不能在 $0$ 点放置陷阱，因为他们害怕青蛙。

您能帮助斯拉夫和米哈伊找出使用陷阱最多能捕捉多少只青蛙吗？

又是一道想法特别的思维、模拟题。

首先虽然这道题的时间限制为3s，但是暴力 $O(N^2)$ 肯定做不了，因为数据范围达到了2e7，所以需要思考出一种绝妙的方法来解决。

如果不能直接枚举来找每个点能被几个青蛙走到，那么又应该如何做呢？

现在思考一个问题，如果一个青蛙能够跳2格，那么它能够到达的格子会有2，4，6 $\dots$ ，即他的步数的倍数，那么我们只需要枚举青蛙一次走过的格子的数量，然后去枚举这样走能够到达的格子的情况，加上相应的数值即可。

CODE：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+10;
#define ll long longvoid solve(){int n;cin >> n;vector<ll>step(n+1);vector<ll>cnt(n+1);for(int i = 0;i < n;i++){int x;cin >> x;if(x <= n)step[x]++;    //记录一步走x格的数量}for(int i = 1;i <= n;i++){  //枚举所有走多少格的情况for(int j = i;j <= n;j+=i){ //枚举走i格的时候，在前n格内，能够走到的所有格cnt[j] += step[i];   //第j格可以有step[i]个青蛙走过}}cout << *max_element(cnt.begin(),cnt.end()) << endl;
}int main(){int t;cin >> t;while(t--){solve();}return 0;
}