目前几乎没有任何算法基础，代码能力极差，只靠那么一丝丝的直觉撑着。菜就多练，艰苦啃题。
E. DivMEX
第一直觉是维护从 1 到 x-1 的前缀 lcm $M(1,2,…,x-1)$ ：$f(l,r)=x$ 意味着 $a_l$ 到 $a_r$ 的 lcm 能被 $M(1,2,…,x-1)$ 整除但不能被 x 整除。
然而维护前缀 lcm 会导致轻易爆 long long 。（天真的我在此卡了一整天）
错误代码展示（里头包含了当时的思路笔记）：
//感觉这题不用考虑那么多个a的lcm。
//一堆数的lcm那是必定被每个数整除的，那直接考虑每个数自己的“不整除mex”就行
//而考虑一个数的“不整除mex”，感觉可以从连乘（n!）入手。
//一个数a被(n-1)!整除但没被n!整除，那a的“不整除mex”就是n。对吗？
//连乘这东西增长的又很快，记下几个就超了题目给的a的范围了
//不对，lcm可能引入新因子
//比如a1含1 2 3因子，a2含4 5因子，那lcm(a1,a2)的mex至少在6以上
//而且上面那个结论也不对。该维护的不是连乘，而是一堆两两互质的数的乘积
//比如1*2*3*4*5*6应该记为1*2*3*2*5*1
//打表出来，24的“互质连乘”是1059261584，远远超过了题目的a的取值范围
//可以以此先计算每个a的mex，储存起来。然后再按l,r组合看会不会出现更高的mex。
//不对，还是得考虑多个a的乘积。考虑之后就不行了，x的可取范围就变成了2*10^5以内的质数幂
vector<ll> getLcm(int a) {
vector<ll> lcm(a,1);
for (int i = 2; i < a; i++) {
lcm[i] = std::lcm(lcm[i - 1], (ll)i);
}
return lcm;
}
bool check(const vector<int>&a, int seg_l, int seg_r, ll L){
ll cur_lcm=1;
for(int i=seg_l;i<=seg_r;i++){
cur_lcm=lcm(gcd(a[i],L),cur_lcm);
if(cur_lcm==L) return true;
}
return false;
}
void solve(const vector<ll> &lcm) {
vector<int> candidates = {2, 3, 4, 5, 7, 8, 9, 11, 13, 16, 17, 19, 23, 25, 27, 29, 31, 32, 37, 41}; //看，这里天真地直接硬编码到41，只考虑了long long上限
int n;
cin >> n;
vector<int> ans;
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for(auto x:candidates){
int i=0;
ll L=lcm[x-1];
while(i<n){
if(a[i]%x==0){
i++;
continue;
}
int seg_l=i;
while(i<n && a[i]%x!=0) i++;
int seg_r=i-1;
if(check(a,seg_l,seg_r,L)){
ans.pb(x);
break;
}
}
}
cout<<ans.size()<<"\n";
sort(ans.begin(),ans.end());
for(auto num:ans){
cout<<num<<" ";
}
cout<<"\n";
}
x 的取值范围是 2*10^5 以内的质数幂。想过基于 x 去搜满足条件的区间，但直接枚举区间很显然会tle。官方题解是基于 a_i 去划分界限去搜 x 的前缀是否全部能被整除。
“we iterate over all 𝑎_𝑖 and check every factor of 𝑎_𝑖 , considering the index 𝑖 as an obstacle.” (官方题解)
此处需要稍微证明一下遍历 𝑎_𝑖 找质数幂因子为什么不会 TLE，因为复杂度目测是 O(n⋅#prime powers) 。 所以这里要补一下质因数分解的知识。
质因数分解、枚举质数幂因子
若 $a=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$，则 $a$ 的所有 prime-power divisors（质数幂因子） 恰好为 $p_i,p_i^2,\ldots,p_i^{e_i}$。因此可以先对 $a$ 做质因数分解，再沿每个质因子不断乘方，直接生成所有质数幂因子，无需从 $1$ 到 $a$ 暴力枚举。
由于每次除去一个质因子后，当前数至少缩小为原来的 $1/2$，所以质因数分解过程中最多进行 $O(\log a)$ 次除法；同时质数幂因子的总数 $e_1+\cdots+e_k\le\log_2 a$。因此，利用预处理的最小质因子 SPF，可以在 $O(\log a)$ 时间内完成质因数分解并枚举 $a$ 的所有 prime-power divisors。
核心代码：
int x = a;
while (x > 1) {
int p = spf[x];
int pw = 1;
while (x % p == 0) {
x /= p;
pw *= p;
process(pw); // p, p^2, ..., p^e
}
}
然后需要对每个区间判断x以下的质因数是否全部能被整除。 这块用线段树，把查询从 $O(x)$ 变成了 $O(\log n)$ 。
对于一个固定的数 q，定义： $$ last[q] = 当前扫描位置之前，最后一个满足 q∣a_i 的位置$$
所以，判断一个区间是否满足要求，等价于对所有 q<x 判断 min(last[q]) 是否在区间内。
总复杂度 $O(n\log ^2 n)$.
先贴上Gemini生成的代码（后面找时间自己重写一番）：
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
// 只需要维护质数幂
vector<int> pp_list;
int pp_id[400005];
struct SegTree {
int n;
vector<int> tree;
SegTree(int n) : n(n), tree(4 * n + 5, 0) {}
void update(int node, int l, int r, int p, int val) {
if (l == r) {
tree[node] = val;
return;
}
int mid = (l + r) >> 1;
if (p <= mid) update(node * 2, l, mid, p, val);
else update(node * 2 + 1, mid + 1, r, p, val);
tree[node] = min(tree[node * 2], tree[node * 2 + 1]);
}
int query(int node, int l, int r, int ql, int qr) {
if (ql > qr) return INF;
if (ql <= l && r <= qr) return tree[node];
int mid = (l + r) >> 1;
int res = INF;
if (ql <= mid) res = min(res, query(node * 2, l, mid, ql, qr));
if (qr > mid) res = min(res, query(node * 2 + 1, mid + 1, r, ql, qr));
return res;
}
};
void solve(const vector<int>& spf) {
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; ++i) cin >> a[i];
int LIM = 2 * n + 5;
// 收集 <= LIM 的质数幂
vector<int> cur_pps;
for (int x : pp_list) {
if (x > LIM) break;
cur_pps.push_back(x);
}
int m = cur_pps.size();
SegTree seg(m);
vector<int> last_pos(LIM + 1, 0);
vector<bool> ok(LIM + 1, false);
for (int i = 1; i <= n; ++i) {
// 分解 a[i] 的质数幂因子
int temp = a[i];
vector<int> my_pp;
while (temp > 1) {
int p = spf[temp];
int pw = p;
while (temp % p == 0) {
my_pp.push_back(pw);
temp /= p;
if (pw <= LIM / p) pw *= p;
}
}
for (int x : my_pp) {
int idx = pp_id[x];
int pre = last_pos[x];
if (idx == 1) { // 最小的质数幂是 2
if (i - pre > 1) ok[x] = true;
} else {
// 查询所有严格小于 x 的质数幂在 [1, idx - 1] 上的最早出现位置
int min_last = seg.query(1, 1, m, 1, idx - 1);
if (min_last > pre) {
ok[x] = true;
}
}
}
for (int x : my_pp) {
int idx = pp_id[x];
last_pos[x] = i;
seg.update(1, 1, m, idx, i);
}
}
// 检查尾部 tail
for (int x : cur_pps) {
int idx = pp_id[x];
int pre = last_pos[x];
if (idx == 1) {
if (n > pre) ok[x] = true;
} else {
int min_last = seg.query(1, 1, m, 1, idx - 1);
if (min_last > pre) {
ok[x] = true;
}
}
}
vector<int> ans;
for (int x : cur_pps) {
if (ok[x]) ans.push_back(x);
}
cout << ans.size() << "\n";
for (int i = 0; i < (int)ans.size(); ++i) {
cout << ans[i] << (i + 1 == (int)ans.size() ? "" : " ");
}
cout << "\n";
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int MAXV = 400005;
vector<int> spf(MAXV + 1);
iota(spf.begin(), spf.end(), 0);
for (int i = 2; i * i <= MAXV; ++i) {
if (spf[i] == i) {
for (int j = i * i; j <= MAXV; j += i) {
if (spf[j] == j) spf[j] = i;
}
}
}
// 预处理全局质数幂列表与离散化映射
for (int p = 2; p <= MAXV; ++p) {
if (spf[p] == p) {
long long pw = p;
while (pw <= MAXV) {
pp_list.push_back((int)pw);
pw *= p;
}
}
}
sort(pp_list.begin(), pp_list.end());
for (int i = 0; i < (int)pp_list.size(); ++i) {
pp_id[pp_list[i]] = i + 1;
}
int t = 1;
cin >> t;
while (t--) {
solve(spf);
}
return 0;
}