ICPC2024 杭州区域赛 M. Make It Divisible 解题报告
题目大意
给你一个长度为 \(n \le 5 \times 10 ^ 4\) 的数列 \(\{a_n\}\) 和一个数 \(m \le 10 ^ 9\)，求出所有满足条件的 \(x\) ，使得对于数列 \(\{a_n + x\}\) 的任意一个区间，满足区间内存在一个数，能整除这个区间内所有的数。输出满足条件的 \(x\) 的个数以及它们的和。
题解
分析
考虑对于一个区间 \([l, r]\)，满足条件的 \(x\) 一定满足：
\[gcd(a_l + x, a_{l + 1} + x, ..., a_{r} + x) = min_{l \le i \le r}\{a_i + x\} \]考虑对于 \(x\) 的普适条件，我们想到可以对 \(gcd\) 进行差分。得到：
\[gcd(a_l + x, a_{l + 1} - a_l, ..., a_{r} - a_{r - 1}) = min_{l \le i \le r}\{a_i + x\} \]令 \(g = gcd(a_{l + 1} - a_l, ..., a_{r} - a_{r - 1})\)，我们可以发现满足条件的 \(mn = min_{l \le i \le r}\{a_i + x\}\) 一定满足 \(mn | g\)。
于是对于一个区间，我们求出他除去第一个元素后的差分数组的区间 \(gcd\)，并弄出他的所有因子。把所有满足 \(mn|a_l\) 的 \(x\) 选出来即可得到这个区间的备选方案。
然后我们考虑对于选取的最小值的点相同的区间，这个区间越大，条件越紧。于是可以自然地想到用笛卡尔树维护这个序列。
然后每次我们按照上面的方法确定了这个区间的备选方案，需要做的就是对所有区间求一个 \(x\) 的交集。我们可以在笛卡尔树上一层一层合并上去即可。集合求交可以考虑用哈希表或 \(set\) 维护。
具体细节
对于区间求 \(gcd\)，我们采用线段树可以将这部分在 \(O(n\log n)\) 的复杂度内完成。
而对于集合求交，我们这边建议选择哈希表。可以在 \(O(|S|)\) 的复杂度内完成集合求交。至于 \(set\)，由于多带了一个 \(\log\)，可能需要更好的常数才可通过，不建议使用。作为复杂度瓶颈，这部分在 \(O(nd)\) 的复杂度内完成，其中 \(d\) 表示约数个数，易知 \(d\le \sqrt n\)。
代码实现
#include<bits/stdc++.h>
#define ull unsigned long long
#define ll long long
#define db double
#define file(a) freopen(#a".in", "r", stdin), freopen(#a".out", "w", stdout)
#define sky fflush(stdout)
#define pc putchar
namespace IO{
const int lim = 1 << 20;
char buf[lim + 3], *p1 = buf, *p2 = buf;
inline char gc(){
if(p1 == p2) p2 = (p1 = buf) + fread(buf,1,lim,stdin);
return p1 == p2 ? EOF : *p1++;
}
template<class T>
inline void read(T &s){
s = 0;char ch = gc();bool f = 0;
while(ch < '0' || '9'<ch) {if(ch == '-') f = 1; ch = gc();}
while('0'<=ch && ch<='9') {s = s * 10 + (ch ^ 48); ch = gc();}
if(ch == '.'){
T p = 0.1;ch = gc();
while('0' <= ch && ch <= '9') {s = s + p * (ch ^ 48);p /= 10;ch = gc();}
}
s = f ? -s : s;
}
template<class T,class ...A>
inline void read(T &s,A &...a){
read(s); read(a...);
}
template<class T>
inline void print(T x){
if(x<0) {x = -x; pc('-');}
static char st[40];
static int top;
top = 0;
do{st[++top] = x - x / 10 * 10 + '0';} while(x /= 10);
while(top) {pc(st[top--]);}
}
template<class T,class ...A>
inline void print(T s,A ...a){
print(s); print(a...);
}
};
using IO::read;
using IO::print;
const int N = 5e4;
int n, m;
int a[N + 3];
int gcd(int a, int b){
if(!b) return a;
return gcd(b, a % b);
}
struct SegTree{
struct node{
int Gcd;
}t[N * 4 + 3];
#define lc(x) (x << 1)
#define rc(x) (x << 1 | 1)
void pushup(int x){
t[x].Gcd = gcd(t[lc(x)].Gcd, t[rc(x)].Gcd);
}
void build(int x, int l, int r){
if(l == r){
t[x].Gcd = a[l] - a[l - 1];
return;
}
int mid = l + r >> 1;
build(lc(x), l, mid);
build(rc(x), mid + 1, r);
pushup(x);
}
int query(int x, int l, int r, int L, int R){
if(L > R) return 0;
if(L <= l && r <= R){
return t[x].Gcd;
}
int mid = l + r >> 1;
int res = 0;
if(L <= mid) res = gcd(res, query(lc(x), l, mid, L, R) );
if(mid + 1 <= R) res = gcd(res, query(rc(x), mid + 1, r, L, R) );
return res;
}
}t;
const int S = 547;
struct HashMap{
int head[S + 3];
int nxt[2000 + 3], to[2000 + 3];
int tot;
inline void clear(){
tot = -1;
memset(head, -1, sizeof(head) );
}
int find(int x){
int u = x % S;
for(int i = head[u]; ~i; i = nxt[i]){
if(to[i] == x){
return true;
}
}
return false;
}
void insert(int x){
int u = x % S;
nxt[++tot] = head[u];
head[u] = tot;
to[tot] = x;
}
}s[N + 3];
int ch[N + 3][2];
int sta[N + 3], top;
int rt;
int l[N + 3], r[N + 3];
std::vector<std::pair<int, int> >tmp1;
std::vector<int>tmp2;
bool any[N + 3];
void calc(int x, int t, int sum){
if(t == tmp1.size() ){
tmp2.push_back(sum);
return;
}
for(int i = 0; i <= tmp1[t].second; ++i){
calc(x, t + 1, sum);
sum *= tmp1[t].first;
}
}
void dfs(int x){
l[x] = r[x] = x;
if(!ch[x][0] && !ch[x][1]){
any[x] = 1;
return;
}
for(int i = 0; i < 2; ++i){
if(ch[x][i]){
dfs(ch[x][i]);
l[x] = std::min(l[x], l[ch[x][i] ]);
r[x] = std::max(r[x], r[ch[x][i] ]);
}
}
int g = t.query(1, 1, n, l[x] + 1, r[x]);
if(g == 0){
any[x] = any[ch[x][0] ] & any[ch[x][1] ];
if(ch[x][0] && ch[x][1]){
int y1 = ch[x][0], y2 = ch[x][1];
for(auto it : s[y1].to){
if(s[y2].find(it) ){
s[x].insert(it);
}
}
}else{
int y = ch[x][0] | ch[x][1];
s[x] = s[y];
}
return;
}
int k = abs(g);
tmp1.clear();
tmp2.clear();
for(int i = 2; i * i <= k; ++i){
if(k % i == 0){
int cnt = 0;
while(k % i == 0) k /= i, ++cnt;
tmp1.push_back({i, cnt});
}
}
if(k != 1) tmp1.push_back({k, 1});
//fprintf(stderr, "%d -> %d %d [%d, %d] %d\n", x, ch[x][0], ch[x][1], l[x], r[x], g);
calc(x, 0, 1);
for(auto it : tmp2){
if(it - a[x] < 1 || it - a[x] > m) continue;
//fprintf(stderr, "%d(%d) ", it - a[x], it);
if((a[l[x] ] + it - a[x]) % it == 0){
bool flag = 1;
if(!any[ch[x][0] ])
if(!s[ch[x][0] ].find(it - a[x] ) )
flag = 0;
if(!any[ch[x][1] ])
if(!s[ch[x][1] ].find(it - a[x] ) )
flag = 0;
if(flag)
s[x].insert(it - a[x] );
//fprintf(stderr, "<-(%d) ", flag);
}
}
/*
fprintf(stderr,"\n%d\n", sz[x]);
for(auto it : s[x].to){
if(it.v) fprintf(stderr, "%d ", it.x);
}
fprintf(stderr,"\n");
*/
}
inline void solve(){
read(n, m);
any[0] = 1;
for(int i = 1; i <= n; ++i){
read(a[i]);
s[i].clear();
ch[i][0] = ch[i][1] = 0;
any[i] = 0;
}
t.build(1, 1, n);
top = 0;
sta[++top] = 1;
for(int i = 2; i <= n; ++i){
int k = top;
while(k && a[sta[k] ] > a[i])
--k;
if(k < top) ch[i][0] = sta[k + 1];
if(k) ch[sta[k] ][1] = i;
sta[++k] = i;
top = k;
}
rt = sta[1];
dfs(rt);
bool flag = 1;
for(int i = 1; i <= n; ++i){
if(!any[i]) flag = 0;
}
if(flag){
printf("%d %lld\n", m, 1ll * (m + 1) * m / 2);
return;
}
ll sum = 0;
for(int i = 0; i <= s[rt].tot; ++i){
sum += s[rt].to[i];
//fprintf(stderr,"%d\n", it);
}
printf("%d %lld\n", s[rt].tot + 1, sum);sky;
}
int main(){
#ifdef LOCAL
file(a);
#endif
int T; read(T);
while(T--){
solve();
fprintf(stderr, "%dms\n", clock() );
}
return 0;
}