[Codeforces Round #275 (Div. 2)]B - Friends and Presents

最近一直在做 codeforces ,总觉得已经刷不动 BZOJ 了? ——真是弱喵

你看连 Div.2 的 B 题都要谢谢题解,不是闲就是傻

显然我没那么闲 ╮(╯_╰)╭

我觉得这题的想法挺妙的~

大意是你需要分别给 a 和 b cnt1 和 cnt2 个数字

但是 a 不要被 x 整除的数 ,as well as,b 不要被 y 整除的数

然后求需要给的最大数的最小值——

最值的最值?那不是典型的二分吗?

但是——坑爹的英文题导致我完全没有意识到这一点……

二分答案 v ,因为 a 不要被 x 整除的数,所以我们可以

先把 被 x 整除的数但不被 y 整除 给b,

再把 被 y 整除的数但不被 x 整除 给a。

然后剔除所有被 a*b 整除的数

剩下的数与 a 和 b 都互素,判一下能不能好好的分配就可以了

代码很好写哦

 #include <cstdio>
#include <cstring> int cnt1, cnt2, x, y;
inline int getint();
inline void putint(long long);
inline bool check(long long); int main()
{
long long l, r, m; cnt1=getint(), cnt2=getint(), x=getint(), y=getint();
l=, r=0x0FFFFFFFFFFFFFFFLL;
while (l+<r)
{
m=(l+r)>>;
if (check(m)) r=m;
else l=m;
}
putint(r); return ;
}
inline int getint()
{
register int num=;
register char ch;
do ch=getchar(); while (ch<'' || ch>'');
do num=num*+ch-'', ch=getchar(); while (ch>='' && ch<='');
return num;
}
inline void putint(long long num)
{
char stack[];
register int top=;
for ( ;num;num/=) stack[++top]=num%+'';
for ( ;top;top--) putchar(stack[top]);
putchar('\n');
}
inline bool check(long long num)
{
long long u=num/x, v=num/y, w=num/(x*y);
long long c1=cnt1, c2=cnt2;
c1-=v-w; c2-=u-w;
if (c1<) c1=; if (c2<) c2=;
if (c1+c2>num-u-v+w) return false;
return true;
}

本傻英文 SB 系列

上一篇:mysql插入一万条数据


下一篇:C语言 百炼成钢9