Codeforeces #1844 A~D题解
A Subtraction Game 博弈论 A+B problem
由于只有两种数字可选，若石子数量为 a + b，先手选完之后必然为 a 或 b，因此后手可以直接选完
B Permutations & Primes 构造
构造方法：3 5 7 9 1 10 8 6 4 2，这样把 1 放中间可以让最多的区间拿到 1，接下来避免同时拿到 2 3，所以把他们放两边，剩下的数字山峰排列最优。
C Particles 思维
可以发现，每次合并的操作都不会改变左右元素的下标奇偶性，比如下标为 1 2 3 的元素，删除中间 2，得到的新元素下标为 1。
所以发现奇数下标和偶数下标形成的集合是独立的，相当于每次在奇数集合或偶数集合删除一个数字，那么直接分别计算答案最后取最大值就好了，贪心选正数。
特判全是负数和 \(n = 1\) 的情况
D Row Major 数论
我们先把每个点向后面第 \(p_i\) 号点连一条边，\(p_i\) 是 \(n\) 的第 \(i\) 个质因数。
设 \(k\) 为第一个不能被 \(n\) 整除的数，则染色以 \(k\) 为一个颜色周期，不断重复。
证明两个结论
- 一个周期内的所有数字都不相同
反证法：同一周期内，假设第 \(i\) 个数字和第 \(j\) 个数字相同，有 \(j - i < k\)。
由于 \(k\) 为第一个不能被 \(n\) 整除的数，所以所有 \(< k\) 的数字 \(p\) 都可以被 \(n\) 整除，也就是存在一条长度为 \(p\) 的边，由于 \(j - i < k\)，所以 第 \(i\) 个数字和第 \(j\) 个数字间存在一条边，因此第 \(i\) 个数字和第 \(j\) 个数字不能相同，矛盾，原命题得证。
- 对于两个数 \(a, b\equiv x\pmod{k}\)，且 \(a \ne b\)，它们的颜色可以相同。
首先令 \(a < b\)，如果不满足，交换 \(a, b\)。
它们之间存在一条边的充要条件是 \(b - a \mid n\)，因为 \(a, b\equiv x\pmod{k}\)，所以 \(b - a = t\cdot k\)，因为 \(k\nmid n\)， 所以 \(xk\nmid n\)，因此 \(a, b\) 之间无边，可以相同。
综上所述，我们完全可以构造一个序列，以 \(k\) 为颜色周期，周期内元素不重复。
时间复杂度：\(O(n)\)。
#include <iostream>
using namespace std;
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T, n;
cin >> T;
while (T--)
{
int k = 1;
cin >> n;
for (; n % k == 0; k++)
;
for (int i = 1; i <= n; i++; i++)
cout << (char)('a' + i % k) << '\n';
}
return 0;
}