题目大意给出一个的值每次可以找一个数满足它们之间不互质使得同时这一次操作可以产生的贡献求最大贡献值。思路首先如果可以白嫖的贡献值不变。考虑和的此时取第一次时此后同上可以把全部取完因为。于是考虑要变成哪个令的个数为那么最终答案是。于是贪心去取即可找到这个最大值。由于的值在十万级别内因数个数大概在 100 左右所以时间复杂度为可以通过。此外注意关键数据要开随手把写上不开见祖宗。理论上可以将常数优化到k的因数的开根级别#includebits/stdc.h using namespace std; const int N 3e5 10; typedef long long ll; int n,k; ll a[N],m,ans,s[N],c[N]; void solve(){ n0; cinmk;ans0; for(int i1,x;im;i){ cinx; if(__gcd(x,k)k) ansx; else a[n]x; } if(k1){ cout0endl;return; } ll cnt0,sum0; for(int i2;i*ik;i){ if(k%i0){ c[cnt]i; if(i*i!k) c[cnt]k/i; } } sort(c1,ccnt1); //for(int i1;icnt;i) coutc[i] ; for(int i1;in;i){ for(int j1;jcntc[j]a[i];j){ if(a[i]%c[j]0){ s[c[j]]a[i]; } } } for(int i1;icnt;i){ //couts[bl[c[i]]] c[i]endl; if(s[c[i]]sum) sums[c[i]]; } for(int i1;icnt;i) s[c[i]]0; coutanssumendl; } int main(){ ios::sync_with_stdio(false); int T;cinT; while(T--) solve(); return 0; }