点击查看目录
目录
- 题面
- 算法思路
- Code
- 我喜欢你
题面
点击查看题面
Samples
输入数据 1
3
3 7
2 5 8
3 2020
20 24 2024
2 5
4 2
输出数据 1
YES
YES
NO
没找到原题。
算法思路
设 \(gcd(w_1,w_2,w_3,……,w_n)=g\)。
容易发现，对于倒满水和清空操作，每个水杯中的数都是 \(g\) 的倍数，并且他们的总和 \(\sum w\) 也是 \(g\) 的倍数。
考虑到对于 \(x\) 向 \(y\) 倒水的操作，对于 \(\sum w\) 贡献为 \(0\)，那么以下两种情况：
- \(x\) 全部倒出，\(a_x=0\) 是 \(g\) 的倍数，除 \(y\) 杯以外，其他杯依然 \(g\) 倍数，总和为 \(g\) 倍数，那么 \(a_y\) 是 \(g\) 倍数显然。
- \(y\) 杯倒满，同理 \(a_x\) 杯是 \(g\) 倍数显然。
因此可以证明，无论多少次操作，杯中的水为 \(g\) 倍数显然。
那么我们设合法的 \(k=t\times gcd(w_x,w_y)\)。
而扩展欧几里得可以得到：
\[\exist x_1,x_2,……,x_n,\sum x_i w_i=g
\]
上式两边同时乘 \(t\)，得到：
\[\exist x_1,x_2,……,x_n,\sum (t x_i) w_i=k
\]
那么 \(t x_i\) 是可以通过加满，倒出和两杯互相倒的方式实现，不难证明。
最终，存在合法的 \(k\) 的充要条件如下：
- \(k<\max{w_i}\)
- \(k\) 是 \(g\) 的倍数
Code
点击查看代码
我喜欢你
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<set>
#include<cstring>
using namespace std;
#define rg register int
#define il inline
typedef long long ll;
namespace io{il ll read(){char c=getchar();int x=0,f=1;while(c<48){if(c=='-')f=-1;c=getchar();}while(c>47)x=(x*10)+(c^48),c=getchar();return x*f;}//快读
}using namespace io;
const int maxn=1e5+50;int T,n,k,w[maxn],maxw,g;int gcd(int x,int y){if(y==0) return x;return gcd(y,x%y);
}int main(){
// #ifndef ONLINE_JUDGE
// freopen("water.in","r",stdin);
// #endifT=read();while(T--){n=read(),k=read();maxw=0;for(rg i=1;i<=n;++i) w[i]=read(),maxw=max(maxw,w[i]);g=w[1];for(rg i=2;i<=n;++i) g=gcd(g,w[i]);if(k<=maxw && k%g==0) printf("YES\n");else printf("NO\n");}return 0;
}