囧仙 的博客

囧仙 的博客

题解 CF483B 【Friends and Presents】

posted on 2020-08-29 21:53:26 | under 题解 |

题目大意

计算出最小的 $V$ ,使得 $1,2,3,\cdots V$ 可以选出两堆,大小分别为 $cnt_1,cnt_2$ ,使得第一堆不包含 $x$ 的倍数,第二堆不包含 $y$ 的倍数。

题解

有一个简单的结论: $1,2,3,\cdots n$ 中,是 $m$ 的倍数的数恰好有 $\left\lfloor\frac{n}{m}\right\rfloor$ 个,为 $m,2\times m,3\times m,\cdots,\left\lfloor\frac{n}{m}\right\rfloor \times m$ 。

两个人都不能选择的数字,显然是 $x\times y$ 的倍数。因此,选出来的答案必定满足 $V-\left\lfloor\frac{V}{x\times y}\right\rfloor \ge cnt_1+cnt_2$ 。同时,这些数中不能被 $x$ 整除的数有 $V-\left\lfloor\frac{V}{x}\right\rfloor$ 个,不能被 $y$ 整除的有 $V-\left\lfloor\frac{V}{y}\right\rfloor$ 个。

于是,我们找到了三个必要的条件:

  • $V-\left\lfloor\frac{V}{x\times y}\right\rfloor \ge cnt_1+cnt_2$ 。

  • $V-\left\lfloor\frac{V}{x}\right\rfloor \ge cnt_1$ 。

  • $V-\left\lfloor\frac{V}{y}\right\rfloor \ge cnt_2$ 。

下证满足这三个条件的 $V$ 必定可以分成两堆,使得这两堆符合题目要求。

由条件一,我们剔除掉 $1,2,3\cdots V$ 中不能放入任意一堆的数,那么剩下来的数的个数必定不小于 $cnt_1+cnt_2$ ,且要么都能被选,要么只能选入某一堆。显然,如果某个数只能放入其中一堆,那么就优先放进去。下面再次分为三个讨论。

  • 如果 $\left\lfloor\frac{V}{x}\right\rfloor \ge cnt_2$ ,且 $\left\lfloor\frac{V}{y}\right\rfloor \ge cnt_1$ ,那么就直接完成目标了。

  • 如果 $\left\lfloor\frac{V}{x}\right\rfloor \ge cnt_1$ ,但 $\left\lfloor\frac{V}{y}\right\rfloor < cnt_2$ ,那么前者会溢出,而后者不够用,还差 $cnt_2-\left\lfloor\frac{V}{y}\right\rfloor$ 个。但是观察可知,

    $$cnt_1+cnt_2-cnt_1=cnt_2\ge cnt_2-\left\lfloor\frac{V}{y}\right\rfloor$$

于是,剩下来的数字已经够用了。

  • 如果 $\left\lfloor\frac{V}{x}\right\rfloor < cnt_1$ ,且 $\left\lfloor\frac{V}{y}\right\rfloor < cnt_2$ ,显然不会有任何数字被浪费,于是能达成目标。

我们终于证明了上面三个条件能符合要求。下面来求出 $V_{min}$ 吧。


首先整理上面的式子:

  • $\left\lfloor\frac{V}{x\times y}\right\rfloor \le V-cnt_1-cnt_2$ 。

  • $\left\lfloor\frac{V}{x}\right\rfloor \le V-cnt_1$ 。

  • $\left\lfloor\frac{V}{y}\right\rfloor\le V-cnt_2$ 。

根据下取整的性质,有:

$$t-1< \lfloor t\rfloor \le t$$

因此,上面三个式子,可以分别转化为:

  • $ \frac{V}{x\times y} -1 <\left\lfloor\frac{V}{x\times y}\right\rfloor \le V-cnt_1-cnt_2$ 。

  • $\frac{V}{x} -1<\left\lfloor\frac{V}{x}\right\rfloor \le V-cnt_1$ 。

  • $\frac{V}{y} -1<\left\lfloor\frac{V}{y}\right\rfloor\le V-cnt_2$ 。

重新整理后,可以得到:

$$\frac{(cnt_1+cnt_2-1)\times x\times y}{x\times y-1}< V,\frac{(cnt_1-1)\times x}{x-1}<V,\frac{(cnt_2-1)\times y}{y-1}<V$$

取最大值即可。

参考代码

#include<bits/stdc++.h>
#define up(l,r,i) for(int i=l;i<=r;i++)
#define dn(l,r,i) for(int i=l;i>=r;i--)
using namespace std;

typedef long long LL;
const int INF =2147483647;
int a,b,x,y,v;
int main(){
    scanf("%d%d%d%d",&a,&b,&x,&y);
    v=max(v,(int)floor((double)(a+b-1)*x*y/(x*y-1)));
    v=max(v,(int)floor((double)(a-1)*x/(x-1)));
    v=max(v,(int)floor((double)(b-1)*y/(y-1)));
    printf("%d\n",v+1);
    return 0;
}