题解 CF483B 【Friends and Presents】

## 题目大意 计算出最小的 $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$$ 取最大值即可。 ## 参考代码 ```cpp #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; } ```