題目鏈接：http://codeforces.com/problemset/problem/483/B

題目意思：有兩個 friends，需要將 cnt1 個不能整除 x 的數(shù)分給第一個friend，cnt2 個不能整除 y 的數(shù)分給第二個friend。x 和 y 都是素數(shù)來的。要求求出最小的 v，v 表示可以從1，2，...，v 中取數(shù)。

? ? 開始我做這條題的時候是用很常規(guī)的方法做的，結果可想而知，WA，MLE，TLE。只能看題解啦，不會嘛～～～題解真是非常清晰、明白、易懂。

? ? 等我用中文來解釋下吧。要用到二分搜索！因為它符合一個條件，如果 v 這個數(shù)符合分配給兩個人的所有條件，那么 v+1 就更加可以啦～～～所以二分是一個好選擇，還有數(shù)據(jù)量太大啦，1e18 ！ 正常做肯定超時！

? ? 首先給出一幅本人嘔心瀝血畫的一幅東西：

? ? 設幾個變量 f1，f2，both，others，f1'，f2'，v。

? ? v：二分枚舉的數(shù)，取值是 1 ～ 1e18，圖中的全集也～～～

? ? f1：能被 x 除盡的個數(shù)，v/f1

? ? f2: 能被 y 除盡的個數(shù)，v/f2 ?

? ? both：同時被 x 和 y 除盡的個數(shù)。由于 x 和 y 都是素數(shù)，所以就相當于能被 x*y 整除。v/(x*y) ?

? ? others: 既不能被 x 也不能被 y 整除的個數(shù)。v - f1 - f2 + both （容斥原理的精髓，both 被減了兩次，所以最終要加回一次）

? ? f1'：能分配給 第二個人（除不盡 y）但又不是從others里面選擇的數(shù)。f1' = f1 - both

? ? f2':?能分配給 第一個人（除不盡 x）但又不是從others里面選擇的數(shù)。f2' = f2 - both

? ? 然后給出的 cnt1 和 cnt2

? ? cnt1 = f2' + others

? ? cnt2 = f1' + others

? ? 那么最終要判斷的是 cnt1 - f2' + cnt2 - f1' 是否 ?<= others 了。因為從 others 里面取的數(shù)都符合分給兩個人的條件。

? ??

1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <algorithm> 6 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); // 注意這個相減有可能為負數(shù)，所以要判斷下 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 = (l+r) >> 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 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/windysai/p/4058235.html

創(chuàng)作挑戰(zhàn)賽新人創(chuàng)作獎勵來咯，堅持創(chuàng)作打卡瓜分現(xiàn)金大獎

總結

以上是生活随笔為你收集整理的codeforces 483B Friends and Presents 解题报告的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。