Dora and C++
分析:
对于两个数x,y
我们想要通过如下操作使得他们的差变得尽可能小
我们要如何操作?
这个操作也就是相当于
d
e
l
=
∣
y
−
x
∣
−
k
1
∗
x
−
k
2
∗
y
del=|y-x|-k_1*x-k_2*y
del=∣y−x∣−k1∗x−k2∗y,让这个差值最小
对于
k
1
∗
x
+
k
2
∗
y
k_1*x+k_2*y
k1∗x+k2∗y这个操作
根据裴蜀定理,我们知道
k
1
x
+
k
2
y
=
k
∗
g
c
d
(
x
,
y
)
k_1x+k_2y=k*gcd(x,y)
k1x+k2y=k∗gcd(x,y)
也就是说通过这个操作得到的数,一定是
g
c
d
(
x
,
y
)
gcd(x,y)
gcd(x,y)的倍数
那么,
M
i
n
(
d
e
l
)
=
∣
y
−
x
∣
%
g
c
d
Min(del)=|y-x|\%gcd
Min(del)=∣y−x∣%gcd
我们对上式的
x
,
y
x,y
x,y用另一种形式表示:
x
=
X
+
k
x
g
c
d
x=X+k_xgcd
x=X+kxgcd
y
=
Y
+
k
y
g
c
d
y=Y+k_ygcd
y=Y+kygcd
∣
y
−
x
∣
=
∣
Y
−
X
+
(
k
y
−
k
x
)
g
c
d
∣
|y-x|=|Y-X+(k_y-k_x)gcd|
∣y−x∣=∣Y−X+(ky−kx)gcd∣
经过
m
o
d
mod
mod意义之后,其实
∣
y
−
x
∣
m
i
n
=
∣
Y
−
X
∣
|y-x|_{min}=|Y-X|
∣y−x∣min=∣Y−X∣
其实就是说,x和y在这个条件下可以等价于
x
%
g
c
d
以及
y
%
g
c
d
x\%gcd以及y\%gcd
x%gcd以及y%gcd
他们的差值最小值也就是取模意义之后两数的差的绝对值
那么对于这道题而言,最小的差值就是每个数 M o d g c d Mod\ gcd Mod gcd意义下的极差。
但是其实并不完全。
比如取模意义后两个数变成0和2,而gcd=3
实际上可以让0+3,再和2去做差
这个其实就类似于一个环形的问题
跨越之后可能让差值更小
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5+100;
int n,x,y;
int a[N];
int gcd(int x,int y){
return y == 0?x:gcd(y,x%y);
}
void Work(){
cin>>n>>x>>y;
int g = gcd(x,y);
for (int i = 1; i <= n; i++) cin>>a[i],a[i]%=g;
sort(a+1,a+n+1);
for (int i = n+1; i <= 2*n; i++) a[i] = a[i-n]+g;
int Min = 1e9+7;
for (int i = 1; i <= n+1; i++)
Min = min(Min,a[i+n-1]-a[i]);
cout<<Min<<endl;
return;
}
signed main(){
int t; cin>>t;
while (t--) Work();
return 0;
}
转载自CSDN-专业IT技术社区
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
原文链接:https://blog.csdn.net/huang_ke_hai/article/details/141861312