Kate and imperfection 2200
https://www.luogu.com.cn/problem/CF1333F
题解：其等价于依次放入一个元素使得每步集合gcd最大值最小。贪心地想，若下一步放入x那么如果有y|x,那么放y一定比放x更优，(y所含因数少)，所以当放入x时，其所有真因数必然都在集合中，故每步答案即为x的最大正因子的值。我们对每个数按最大正因子由小到大排序，即为答案。
#include<bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for(int i=a;i<=b;i++)
const int N=5e5+1;
int n,a[N],c[N];
int main(){
cin>>n;
FOR(i,1,n)FOR(j,2,n/i)a[i*j]=i;
FOR(i,1,n)c[a[i]]++;
FOR(i,1,n)while(c[i]--)cout<<i<<' ';
return 0;
}
E. Carrots for Rabbits 2200
https://www.luogu.com.cn/problem/CF1428E
题解：显然每个胡萝卜均分所产生平方和最小，将x分为k份，则会有x%k份为\(\lfloor x/k\rfloor\) +1,y-(x%k)份为\(\lfloor x/k \rfloor\),我们又发现，分的份数越多，其减小的数值越小，故我们可以贪心：将分成k份-分成k+1份的值放入大根堆里，每次取首并将其从f(k)-f(k+1)->f(k+1)-f(k+1)放回大根堆中，这样操作直至满足，所得答案最小。
至于为什么分的份数越多减小的值越小有大佬给出了证明：令f(x,k)表示把x分为k份所得的平方和，则我们需证f(x,y)-f(x,y+1)>=f(x,y+1)-f(x,y+2).我们首先移项，即为f(x,y)+f(x,y+2)>=2f(x,y+1)，由将两个x分为2个y+1份等价于把2x分为（2y+2)份（分完后f(x,y+1)序列中数值为x/(y+1)+1和x/(y+1),f(2x,2y+2)为x/(y+1)+1,x/(y+1),一致，而分成这两个数值时对应个数一定相等，故等价。而将2x一边分为y分另一边分为y+2份一定比f(2x,2y+2)劣，故证毕。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+10;
int a[N];
struct node{
int x,y,z;
bool operator < (const node&W) const
{
return x<W.x;
}
};
int get(int x,int k)
{
int s=x/k;
int t=x%k;
return s*s*(k-t)+t*(s+1)*(s+1);
}
priority_queue<node> q;
signed main()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;i++)
cin>>a[i];
int sum=0;
for(int i=1;i<=n;i++)
{
sum+=a[i]*a[i];
q.push({get(a[i],1)-get(a[i],2),a[i],2});
}
for(int i=1;i<=k-n;i++)
{
auto t=q.top();
q.pop();
int x=t.x,y=t.y,z=t.z;
sum-=x;
q.push({get(y,z)-get(y,z+1),y,z+1});
}
cout<<sum<<endl;
}
D. Koxia and Game 2000
https://codeforces.com/problemset/problem/1770/D
题解：易知想要使得1->n各出现一次，必须使得每一步都在掌控之中（即两数相等不给他选）否则他一定可以破坏排列。
那么，对于ai=bi,ci可取n个值，而对于其他情况ci必须与ai或bi相等。考虑构建图，ai与 bi相连，若从x走到与其相连的y则视为此步中舍弃x选择y，故对于图中的每一个连通块，必须有一个环（当然至多只有一个否则无解），即为一个基环树（自环也可），每个非自环基环树有两种遍历方法，自环树有n种遍历方法，结合并查集遍历即可。(参考了大佬代码)
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+100;
const int mod=998244353;
int ok,v[N],a[N],b[N],tot,c[N],fa[N],sm[N],siz[N];
template <typename T> void read(T &t) {
t=0; char ch=getchar(); int f=1;
while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); }
do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f;
}
template <typename T> void write(T t) {
if (t<0) { putchar('-'); write(-t); return; }
if (t>9) write(t/10);
putchar('0'+t%10);
}
int qpow(int x,int y){
int ans=1;
while(y){
if(y&1) ans=ans*x%mod;
x=x*x%mod;
y>>=1;
}
return ans;
}
int find(int x){
if(x==fa[x]) return x;
return fa[x]=find(fa[x]);
}
void merge(int x,int y){
int u=find(x),v=find(y);
if(u==v) return;
fa[v]=u;
siz[u]+=siz[v];sm[u]+=sm[v];
}
void solve(){
int n;read(n);
int ans=1,cnt=0;
for(int i=1;i<=n;i++) read(a[i]),fa[i]=i,sm[i]=0,siz[i]=1,c[i]=0;
for(int i=1;i<=n;i++) read(b[i]);
for(int i=1;i<=n;i++){
if(a[i]==b[i]) cnt++,sm[a[i]]=1;
}
for(int i=1;i<=n;i++){
if(a[i]==b[i]) continue;
merge(a[i],b[i]);
}
for(int i=1;i<=n;i++)
c[find(a[i])]++;
for(int i=1;i<=n;i++){
if(find(i)!=i) continue;
if(c[i]!=siz[i]) ans=0;
else if(sm[i]) ans=ans*n%mod;
else ans=ans*2%mod;
}
write(ans);puts("");
}
signed main(){
int T;cin>>T;
while(T--) solve();
}