【偶然一题】CF1979C. Earning on Bets | 思维 | 绕证明绕出来了

本文主要是介绍【偶然一题】CF1979C. Earning on Bets | 思维 | 绕证明绕出来了，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目内容

原题链接

给你一个长度为 $n$ 的数组 $a$ ，让你构造一个数组 $b$ ，
满足对于 $1\le i\le n$， 都有 $a_i\times b_i>\sum _{j=1}^n{b}_j$

数据范围

• $1\le n\le 50$
• $2\le a_i\le 20$

题解

令 $sum=b_1+b_2+\cdots +b_n$

根据 $a_i\times b_i>sum$，有 $b_i>\lfloor \frac{sum}{a_i}\rfloor +1>\frac{sum}{a_i}(存在小数)$

故 $b_i>\frac{sum}{a_i}$

故 $b_1+b_2+\cdots +b_n>\frac{sum}{a_1}+\frac{sum}{a_2}+\cdots \frac{sum}{a_n}$

有 $sum>sum\times (\frac{1}{a_1}+\frac{1}{a_2}+\cdots \frac{1}{a_n})$

约分得到 $1>1\times (\frac{1}{a_1}+\frac{1}{a_2}+\cdots \frac{1}{a_n})$

即给定的数组 $a$ 满足上述条件则是有答案的。

但是小数存在计算误差，我们只需要选择一个合适的 $sum$ 即可，这个数最小是所有 $a_i$ 的最小公倍数。

计算后进行判断即可。

时间复杂度：$O(n\log \max (a_i))$

代码

#include <bits/stdc++.h>
using namespace std;int lcm(int a, int b) {return int(1ll * a * b / gcd(a, b));
}void solve() {int n;cin >> n;vector<int> a(n);int g = 1;for (int i = 0; i < n; ++i) {cin >> a[i];g = lcm(g, a[i]);}long long sum = 0;for (int i = 0; i < n; ++i) {sum += g / a[i];}if (sum >= g) {cout << "-1\n";return;}for (int i = 0; i < n; ++i) {cout << g / a[i] << " \n"[i + 1 == n];}
}int main()
{ios::sync_with_stdio(false);cin.tie(nullptr);int T = 1;cin >> T;while (T--) {solve();}return 0;
}

这篇关于【偶然一题】CF1979C. Earning on Bets | 思维 | 绕证明绕出来了的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---