发现还没有和我一样的做法。
觉得 B 比 A 好想的多。
令 \(A_i\) 为 \(a_i\) 变成 \(A\) 的倍数最少次数，\(B_i,C_i,AB_i,AC_i,BC_i,ABC_i\) 同理。
那么我们就有 \(A_i=(A-A\bmod {a_i})\bmod A\)，其他同理。
这一大坨东西显然都能在 \(O(n)\) 的时间复杂度内算出来。
剩下的就很好写了。
先把所有的东西排个序。
如果 \(n\geq 3\)，那么可以用 \(A_i,B_i,C_i\) 的每一个的前三个来计算答案。
如果 \(n\geq 2\)，那么可以用 \(AB_i,AC_i,BC_i\) 的每一个的前两个来计算答案。
如果 \(n\geq 3\)，那么可以用 \(ABC_i\) 来计算答案。
最后取个 \(\min\) 就好了。
记得判断取的数是不是同一个数。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
const int mod=998244353;
const int N=2e5+10;
const ll inf=1e18;
int T;
int n,m,q;
ll a,b,c;
ll ab,ac,bc,abc;
ll p;
ll gcd(ll x,ll y)
{
if(!y) return x;
return gcd(y,x%y);
}
ll lcm(ll x,ll y)
{
return x*y/gcd(x,y);
}
struct num
{
ll num;
int id;
}A[N],B[N],C[N],AB[N],AC[N],BC[N],ABC[N];
bool cmp(num x,num y)
{
return x.num<y.num;
}
ll ans=inf;
int main()
{
scanf("%d%lld%lld%lld",&n,&a,&b,&c);
ab=lcm(a,b);
bc=lcm(b,c);
ac=lcm(a,c);
abc=lcm(a,lcm(b,c));
for(int i=1;i<=n;i++)
{
scanf("%lld",&p);
//这一部分当时赛时 sb 了写得比较复杂，可以直接用上文的式子来计算。
A[i]=num{p%a?a-p%a:0,i};
B[i]=num{p%b?b-p%b:0,i};
C[i]=num{p%c?c-p%c:0,i};
AB[i]=num{p%ab?ab-p%ab:0,i};
AC[i]=num{p%ac?ac-p%ac:0,i};
BC[i]=num{p%bc?bc-p%bc:0,i};
ABC[i]=num{p%abc?abc-p%abc:0,i};
}
sort(A+1,A+1+n,cmp);
sort(B+1,B+1+n,cmp);
sort(C+1,C+1+n,cmp);
sort(AB+1,AB+1+n,cmp);
sort(AC+1,AC+1+n,cmp);
sort(BC+1,BC+1+n,cmp);
sort(ABC+1,ABC+1+n,cmp);
if(n>=3)
{
for(int i=1;i<=3;i++)
for(int j=1;j<=3;j++)
for(int k=1;k<=3;k++)
{
if(A[i].id!=B[j].id&&B[j].id!=C[k].id&&A[i].id!=C[k].id) ans=min(ans,A[i].num+B[j].num+C[k].num);
}
}
if(n>=2)
{
for(int i=1;i<=2;i++)
for(int j=1;j<=2;j++)
{
if(AB[i].id!=C[j].id) ans=min(ans,AB[i].num+C[j].num);
}
for(int i=1;i<=2;i++)
for(int j=1;j<=2;j++)
{
if(AC[i].id!=B[j].id) ans=min(ans,AC[i].num+B[j].num);
}
for(int i=1;i<=2;i++)
for(int j=1;j<=2;j++)
{
if(BC[i].id!=A[j].id) ans=min(ans,BC[i].num+A[j].num);
}
}
ans=min(ans,ABC[1].num);
printf("%lld",ans);
return 0;
}