【CF补题&&数学&&裴蜀定理】 div969 C Dora and C++
Dora and C++https://i-blog.csdnimg.cn/direct/41078a7c10a84dcb94cca20a69403449.png
分析：
对于两个数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;
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,a%=g;
sort(a+1,a+n+1);
for (int i = n+1; i <= 2*n; i++) a = a+g;
int Min = 1e9+7;
for (int i = 1; i <= n+1; i++)
Min = min(Min,a-a);
cout<<Min<<endl;
return;
}
signed main(){
int t; cin>>t;
while (t--) Work();
return 0;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]