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(数学)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。