CF1478A - Nezzar and Colorful Balls

Solution

真不戳，这$A$题真不戳，我直接好家伙。

讲一下我搞了半个小时的垃圾做法 （好吧后来看了看标算好像和我是一样的） 。
大概是容易发现你两个数$(x,y)$做来做去最后一定是$ax-(a-1)y$的形式，然后再继续搞一搞三个数的，最后你发现每个数的贡献次数之和等于$1$，于是问题变成了这样子：
给定$a_1...a_n$，问是否存在一个$x_1...x_n$，使得：
$$\begin{gathered} \sum _{i=1}^n{x}_i=1 \\ \sum _{i=1}^n{a}_i{x}_i=k \end{gathered}$$
从上面的式子可知：
$$x_n=1-\sum _{i=1}^{n-1}{x}_i$$
代入下面的式子：
$$\sum _{i=1}^n{a}_i{x}_i=\sum _{i=1}^{n-1}{a}_i{x}_i+a_n(1-\sum _{i=1}^{n-1}{x}_i)=\sum _{i=1}^{n-1}(a_i-a_n)x_i+a_n$$
于是我们有：
$$\sum _{i=1}^{n-1}(a_i-a_n)x_i=k-a_n$$
那么就是一个${\sum }_i{a}_i{x}_i=b$的裴蜀定理的形式，有解的条件就是：
$$gcd(a_i-a_n)|k-a_n$$
注意这里为了避免$a_i-a_n<0$，我们给降序序列排序，于是$a_n$为最小值。

时间复杂度$O(nlgn)$。

然后就没了，对，就没了。我真是个铁憨憨。

Code

#include <vector> #include <list> #include <map> #include <set> #include <deque> #include <queue> #include <stack> #include <bitset> #include <algorithm> #include <functional> #include <numeric> #include <utility> #include <sstream> #include <iostream> #include <iomanip> #include <cstdio> #include <cmath> #include <cstdlib> #include <cctype> #include <string> #include <cstring> #include <ctime> #include <cassert> #include <string.h> //#include <unordered_set> //#include <unordered_map> //#include <bits/stdc++.h>#define MP(A,B) make_pair(A,B) #define PB(A) push_back(A) #define SIZE(A) ((int)A.size()) #define LEN(A) ((int)A.length()) #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define fi first #define se secondusing namespace std;template<typename T>inline bool upmin(T &x,T y) { return y<x?x=y,1:0; } template<typename T>inline bool upmax(T &x,T y) { return x<y?x=y,1:0; }typedef long long ll; typedef unsigned long long ull; typedef long double lod; typedef pair<int,int> PR; typedef vector<int> VI;const lod eps=1e-11; const lod pi=acos(-1); const int oo=1<<30; const ll loo=1ll<<62; const int mods=998244353; const int MAXN=600005; const int INF=0x3f3f3f3f;//1061109567 /*--------------------------------------------------------------------*/ inline ll read() {ll f=1,x=0; char c=getchar();while (c<'0'||c>'9') { if (c=='-') f=-1; c=getchar(); }while (c>='0'&&c<='9') { x=(x<<3)+(x<<1)+(c^48); c=getchar(); }return x*f; } ll a[MAXN]; ll gcd(ll x,ll y) { return y==0?x:gcd(y,x%y); } signed main() {int Case=read();while (Case--){int n=read(); ll k=read(),g=0;for (int i=1;i<=n;i++) a[i]=read();sort(a+1,a+n+1,greater<ll>());for (int i=1;i<n;i++) a[i]-=a[n]; k-=a[n];for (int i=1;i<n;i++) g=gcd(g,a[i]);puts(k%g==0?"YES":"NO");} return 0; }

总结

以上是生活随笔为你收集整理的CF1478A - Nezzar and Colorful Ball(数学)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。