题解：P16392 [IATI 2024] Lex_gcd
lailai0916
·
·
题解
题意简述
给定一个正整数序列。
可以选择一个元素乘以质数 p，也可以不操作。
随后任意排列序列。
要求任意 K 个位置上的最大公约数都保持不变。
求字典序最小的可行序列。
解题思路
先不进行乘法操作。
固定质数 q。
记 e_i(q) 为 a_i 中 q 的指数，
记 t_q 为全部指数中的第 K 大值。
对固定位置 i，考虑所有包含它的 K 元集合。
这些集合的最小指数所能达到的最大值为：
\max_{\substack{i\in S\\|S|=K}}\min_{j\in S}e_j(q)=\min(e_i(q),t_q)
这是因为指数严格大于 t_q 的位置至多有 K-1 个。
而指数不小于 t_q 的位置至少有 K 个。
所以，全部 K 元集合的最大公约数，
能够确定每个位置的截断指数。
反过来，任取 K 个位置。
其中至少有一个位置的指数不超过 t_q。
因此，截断不会改变这 K 个指数的最小值。
于是，两种排列等价，
当且仅当每个位置的全部截断指数相同。
定义位置 i 的特征值：
h_i=\prod_q q^{\min(e_i(q),t_q)}
只有特征值相同的两个位置可以交换元素。
把相同特征值的位置分成一组。
组内位置升序排列，数值也升序排列，
再按顺序一一对应。
每个组都这样放置，
就得到不进行乘法时的字典序最小序列。
记这个序列为基准序列。
下面分析把 a_i 乘以 p 的影响。
只有质数 p 的指数可能改变。
若 e_i(p)\ge t_p，
旧特征值不会直接改变。
第 K 大指数可能保持不变，也可能增加。
若阈值不变，新的分组与旧分组相同。
若阈值增加，新分组只是旧分组的进一步细分。
在任一情况下，
把结果中的 pa_i 换回 a_i，
都会得到一个旧问题的合法排列，
且这个排列严格更小。
基准序列已经是旧问题的最小排列。
所以，这些操作不可能改进答案。
唯一需要考虑的是：
e_i(p)<t_p
此时阈值保持不变，
位置 i 的特征值会从 h_i 变成 ph_i。
也就是说，只把一个位置和一个数值移到另一个组。
若特征值 ph_i 的组原本不存在，
新组只包含位置 i 与数值 pa_i。
设 i 在原组中的位置排名为 r，
若 $s<r$，删除后更早的位置会得到更大的数。
若 $s=r$，位置 $i$ 本身会变大。
若 $s>r$，位置 $i$ 仍先于可能变小的位置，
而它得到的 $pa_i$ 大于基准值。
所以，目标组原本不存在时也无法改进答案。
现在只需枚举满足条件的原组，
且目标组 $ph_i$ 已经存在的元素。
对每个特征组，同时保存：
- 按数值排序的二元组
- 按位置排序的下标序列
从原组删除位置 $i$ 与数值 $a_i$ 时，
只有两个排名之间的一段会移动一位。
向目标组插入位置 $i$ 与数值 $pa_i$ 时同理。
两个移动区间的端点都能通过二分求出。
字典序只取决于最早发生变化的位置。
每段移动只需记录它的第一个新值。
加上位置 $i$ 自身，
一个候选至多需要记录三个变化点。
代码用固定长度的 `Change` 保存这些变化。
比较两个候选时，
按位置合并变化点，未记录的位置读取基准值。
第一次出现不同数值即可决定字典序。
相同的 $a_i$ 可能对应多个下标。
第一轮先确定最优的原组与被乘数数值。
再删除一份该数值，构造临时基准序列。
第二轮只重新枚举这个原组的下标。
这样可以精确处理相等数值，
不需要随机截断候选集合。
最后，将选中的 $a_i$ 乘以 $p$，
重新构造一次特征组与答案。
特征值构造需要分解所有数。
相同数值的质因数分解完全相同。
代码按数值缓存分解结果，
第二次构造时也会复用原有缓存。
若 $p\ge40000$，修改后的数可能超过 $10^9$。
先除去质因子 $p$，
剩余部分仍不超过原数上界。
之后试除所有小于 $40000$ 的质数即可。
除质因数分解外，
排序、分组与候选比较需要 $O(n\log n)$ 时间。
空间复杂度为 $O(n\log A)$，
其中 $A$ 是输入数值上界。
## 参考代码
```cpp
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
using pli=pair<ll,int>;
using pil=pair<int,ll>;
const int V=40000;
struct Group
{
vector<pli> val;
vector<int> pos;
};
struct Change
{
pil a[3];
int n;
};
using Groups=map<ll,Group>;
int n,k;
ll p;
bool vis[V];
vector<int> pri;
vector<ll> a;
map<ll,vector<pli>> cache;
void init()
{
for(int i=2;i<V;i++)
{
if(vis[i])continue;
pri.push_back(i);
for(int j=i+i;j<V;j+=i)vis[j]=1;
}
}
const vector<pli> &factor(ll x)
{
auto [it,ok]=cache.emplace(x,vector<pli>());
if(!ok)return it->second;
vector<pli> &res=it->second;
ll v=x;
if(p>=V&&v%p==0)
{
int c=0;
while(v%p==0)
{
v/=p;
c++;
}
res.push_back({p,c});
}
for(int q:pri)
{
if((ll)q*q>v)break;
if(v%q)continue;
int c=0;
while(v%q==0)
{
v/=q;
c++;
}
res.push_back({q,c});
}
if(v>1)res.push_back({v,1});
return res;
}
pair<vector<ll>,Groups> build(const vector<ll> &src)
{
map<ll,vector<int>> cnt;
vector<const vector<pli> *> fac(n);
for(int i=0;i<n;i++)
{
fac[i]=&factor(src[i]);
for(auto [q,e]:*fac[i])cnt[q].push_back(e);
}
map<ll,int> lim;
for(auto &[q,v]:cnt)
{
sort(v.begin(),v.end());
int m=v.size();
if(m>=k)lim[q]=v[m-k];
}
Groups g;
for(int i=0;i<n;i++)
{
ll v=1;
for(auto [q,e]:*fac[i])
{
int c=min(e,lim[q]);
while(c--)v*=q;
}
g[v].val.push_back({src[i],i});
}
vector<ll> ans(n);
for(auto &[key,t]:g)
{
int m=t.val.size();
t.pos.resize(m);
for(int i=0;i<m;i++)t.pos[i]=t.val[i].second;
sort(t.pos.begin(),t.pos.end());
sort(t.val.begin(),t.val.end());
for(int i=0;i<m;i++)ans[t.pos[i]]=t.val[i].first;
}
return {move(ans),move(g)};
}
int get_up(const Group &g,ll v,int id)
{
int m=g.val.size();
int q=upper_bound(g.val.begin(),g.val.end(),make_pair(v,n))-g.val.begin();
if(q==m)
{
q--;
if(g.pos[q]<id)return id;
}
else if(g.pos[q]>id)
{
if(!q)return id;
q--;
if(g.pos[q]<id)return id;
}
return g.pos[q];
}
int get_down(const Group &g,ll v)
{
int q=upper_bound(g.val.begin(),g.val.end(),make_pair(v,n))-g.val.begin();
return g.pos[q-1];
}
bool cmp(const Change &u,const Change &v,const vector<ll> &base)
{
int i=0,j=0;
while(i<u.n||j<v.n)
{
int pu=i<u.n?u.a[i].first:n;
int pv=j<v.n?v.a[j].first:n;
int id=min(pu,pv);
ll x=pu==id?u.a[i++].second:base[id];
ll y=pv==id?v.a[j++].second:base[id];
if(x!=y)return x<y;
}
return 0;
}
void try_group(ll key,Group &v,Change &best,int &best_id,ll &best_key,Groups &g,const vector<ll> &base,const vector<ll> &tmp)
{
auto it=g.find(key*p);
if(it==g.end())return;
Group &u=it->second;
for(int id:v.pos)
{
ll val=a[id]*p;
int up=get_up(u,val,id);
int down=get_down(v,a[id]);
if(down<min(up,id)||up==id)continue;
Change cur={};
if(up>id)
{
auto q=upper_bound(u.pos.begin(),u.pos.end(),id);
int next=*q;
if(base[next]>a[id])continue;
cur.a[cur.n++]={id,base[next]};
}
else
{
cur.a[cur.n++]={up,val};
auto q=lower_bound(u.pos.begin(),u.pos.end(),id);
q--;
cur.a[cur.n++]={id,base[*q]};
}
if(down<id)
{
auto q=upper_bound(v.pos.begin(),v.pos.end(),down);
cur.a[cur.n++]={down,base[*q]};
}
for(int i=0;i<cur.n;i++)
{
for(int j=i+1;j<cur.n;j++)if(cur.a[j]<cur.a[i])swap(cur.a[i],cur.a[j]);
}
if(cmp(cur,best,tmp))
{
best=cur;
best_id=id;
best_key=key;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
init();
int t;
cin>>t;
while(t--)
{
cin>>n>>k>>p;
cache.clear();
a.resize(n);
for(int i=0;i<n;i++)cin>>a[i];
auto res=build(a);
vector<ll> base=move(res.first);
Groups g=move(res.second);
vector<ll> ans=base;
if(p!=1)
{
Change best={};
int id=-1;
ll key=0;
for(auto &[v,u]:g)try_group(v,u,best,id,key,g,base,base);
if(id!=-1)
{
Group &v=g[key];
int m=v.pos.size();
int down=get_down(v,a[id]);
vector<ll> tmp=base;
for(int i=0;i+1<m;i++)if(v.pos[i]>=down)tmp[v.pos[i]]=tmp[v.pos[i+1]];
best={};
id=-1;
try_group(key,v,best,id,key,g,base,tmp);
a[id]*=p;
ans=build(a).first;
}
}
for(int i=0;i<n;i++)
{
if(i)cout<<' ';
cout<<ans[i];
}
cout<<'\n';
}
return 0;
}
```