题解 | #好好好数组#

注意到数据范围：

$1≤T≤10^5, 1\le m\le n\le 10^7$

很显然不能通过遍历等操作来处理。

但这不代表我们不能打表找规律。

注意到 $\forall i\in [1,n), a_i=a_{i+1}\bmod i$

所以只需要确定 $a_n$ 的值，便可确定整个数组。

所以从 0 到 n 枚举 $a_n$ ，构造出数组并输出出来找规律

打表代码：

vector<int> a(n + 7);
for (int i = 0; i <= n; i++)
{
	map<int, int> T;
	T[a[n] = i] = 1;
	for (int j = n - 1; j > 0; j--)
	{
		a[j] = a[j + 1] % j;
		T[a[j]] = 1;
	}
	cout << T.size() << '\n';
	if (T.size() >= m)
	{
		for (int j = 1; j <= n; j++)
			cerr << a[j] << ' ';
		cerr << '\n';
	}
}

题目样例太小，不适合打表，所以输入：

1
10 0

得到

0 0 0 0 0 0 0 0 0 0 
0 1 1 1 1 1 1 1 1 1 
0 0 2 2 2 2 2 2 2 2 
0 0 0 3 3 3 3 3 3 3 
0 0 0 0 4 4 4 4 4 4 
0 0 0 0 0 5 5 5 5 5 
0 0 0 0 0 0 6 6 6 6 
0 0 0 0 0 0 0 7 7 7 
0 0 0 0 0 0 0 0 8 8 
0 0 0 0 0 0 0 0 0 9 
0 1 1 1 1 1 1 1 1 10

观察到，输出共包含了 3 种情况：

$a_n = 0$

此时整个数组均为 $0$ ；
$a_n\in [2,n-1]$

此时，整个数组被 $a_n$ 分为两部分， $[1,a_n]$ 为 $0$ ， $[a_n+1,n]$ 为 $a_n$ ；
$a_n = n$

此时数组被分为三部分， $a_1=0,a_n=n,a_i=1(i\in [2,n-1])$ 。

故分析出：

ans= \left\{ \begin{array}{ll} n+1, & \text{if } m = 1; \\ n, & \text{if } m = 2; \\ 1, & \text{if } m = 3; \\ 0, & \text{otherwise.} \end{array} \right.

代码：

#include <bits/stdc++.h>
using namespace std;
void _()
{
    int n, m;
    cin >> n >> m;
    switch (m)
    {
    case 1:
        cout << n + 1 << '\n';
        break;
    case 2:
        cout << n << '\n';
        break;
    case 3:
        cout << 1 << '\n';
        break;
    default:
        cout << 0 << '\n';
        break;
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int T;
    cin >> T;
    while (T--)
        _();
    return 0;
}