建筑网站、,小红书怎么推广自己的产品,dedecms网站二次开发,海口装饰设计网站建设题目链接#xff1a;http://codeforces.com/problemset/problem/483/B 题目意思#xff1a;有两个 friends#xff0c;需要将 cnt1 个不能整除 x 的数分给第一个friend#xff0c;cnt2 个不能整除 y 的数分给第二个friend。x 和 y 都是素数来的。要求求出最小的 v#xff…题目链接http://codeforces.com/problemset/problem/483/B 题目意思有两个 friends需要将 cnt1 个不能整除 x 的数分给第一个friendcnt2 个不能整除 y 的数分给第二个friend。x 和 y 都是素数来的。要求求出最小的 vv 表示可以从12...v 中取数。 开始我做这条题的时候是用很常规的方法做的结果可想而知WAMLETLE。只能看题解啦不会嘛题解真是非常清晰、明白、易懂。 等我用中文来解释下吧。要用到二分搜索因为它符合一个条件如果 v 这个数符合分配给两个人的所有条件那么 v1 就更加可以啦所以二分是一个好选择还有数据量太大啦1e18 正常做肯定超时 首先给出一幅本人呕心沥血画的一幅东西 设几个变量 f1f2bothothersf1f2v。 v二分枚举的数取值是 1 1e18图中的全集也 f1能被 x 除尽的个数v/f1 f2: 能被 y 除尽的个数v/f2 both同时被 x 和 y 除尽的个数。由于 x 和 y 都是素数所以就相当于能被 x*y 整除。v/(x*y) others: 既不能被 x 也不能被 y 整除的个数。v - f1 - f2 both 容斥原理的精髓both 被减了两次所以最终要加回一次 f1能分配给 第二个人除不尽 y但又不是从others里面选择的数。f1 f1 - both f2: 能分配给 第一个人除不尽 x但又不是从others里面选择的数。f2 f2 - both 然后给出的 cnt1 和 cnt2 cnt1 f2 others cnt2 f1 others 那么最终要判断的是 cnt1 - f2 cnt2 - f1 是否 others 了。因为从 others 里面取的数都符合分给两个人的条件。 1 #include iostream2 #include cstdio3 #include cstdlib4 #include cstring5 #include algorithm6 using namespace std;7 8 typedef __int64 LL;9 LL cnt1, cnt2, x, y;
10
11 bool check(LL v)
12 {
13 LL f1 v / x;
14 LL f2 v / y;
15 LL both v / (x*y);
16 LL others v - f1 - f2 both;
17 LL ff1 f1 - both; // second
18 LL ff2 f2 - both; // first
19
20 LL gf1 (cnt1 - ff2 0 ? cnt1 - ff2 : 0); // 注意这个相减有可能为负数所以要判断下
21 LL gf2 (cnt2 - ff1 0 ? cnt2 - ff1 : 0);
22
23 return (gf1 gf2 others);
24 }
25
26 int main()
27 {
28 while (scanf(%I64d%I64d%I64d%I64d, cnt1, cnt2, x, y) ! EOF)
29 {
30 LL l 1, r 1e18;
31 while (l r)
32 {
33 LL m (lr) 1;
34 if (check(m))
35 r m;
36 else
37 l m 1;
38 }
39 printf(%I64d\n, r);
40 }
41 return 0;
42 } 转载于:https://www.cnblogs.com/windysai/p/4058235.html
