汉堡猪猪分糖果【牛客tracker 每日一题】

汉堡猪猪分糖果时间限制1秒 空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述汉堡猪猪有n nn颗糖果准备分给m mm位小朋友且要求每位小朋友至少获得一颗糖果。设最后第j jj位小朋友得到的糖果数为c j c_jcj​则有c 1 c 2 ⋯ c m n , c j ≧ 1 c_1c_2⋯c_mn,c_j≧1c1​c2​⋯cm​n,cj​≧1。汉堡猪猪关注分配结果的按位与值c 1 c 2 … c m c_1 \\ c_2 \\ … \\ c_mc1​c2​…cm​并想让该值尽可能大。请你帮他计算在最优分配下该按位与的最大可能值。输入描述每个测试文件包含多组测试数据。第一行输入整数T ( 1 ≦ T ≦ 10 5 ) T(1≦T≦10^5)T(1≦T≦105)表示数据组数。随后T TT行每行输入两个整数n , m ( 1 ≦ m ≦ n ≦ 10 9 ) n,m(1≦m≦n≦10^9)n,m(1≦m≦n≦109)表示糖果总数与小朋友人数。输出描述对每组测试数据输出一行表示在满足c j ≧ 1 c_j≧1cj​≧1的前提下c 1 c 2 … c m c_1 \\ c_2 \\ … \\ c_mc1​c2​…cm​的最大可能值。示例1输入4 8 3 3 2 5 1 514114 114514输出2 0 5 4解题思路本题核心是通过二进制贪心枚举求解按位与的最大值按位与的最大值由最高位的有效二进制位决定因此从高位到低位33 3333位覆盖1 e 9 1e91e9的二进制范围遍历2的幂次预处理2 22的幂次数组对每个二进制位a [ i ] a[i]a[i]判断能否让所有小朋友的糖果数都包含该位即每个小朋友至少有a [ i ] a[i]a[i]颗且基础满足至少1 11颗若总需求n × a [ i ] ≤ n×a[i]≤n×a[i]≤剩余糖果数则保留该位并扣除对应糖果数将a [ i ] a[i]a[i]加入答案否则跳过该位。最后处理n m nmnm的特殊情况所有小朋友各1 11颗按位与为1 11。该方法每次仅遍历30 3030位时间复杂度O ( T × 30 ) O(T×30)O(T×30)适配T ≤ 1 e 5 、 n , m ≤ 1 e 9 T≤1e5、n,m≤1e9T≤1e5、n,m≤1e9的规模精准找到最优按位与值。总结核心逻辑从高位到低位贪心枚举二进制位判断该位能否保留所有数的该位为1 11最大化按位与值。关键操作预处理2 22的幂次数组遍历每位时验证总需求是否≤剩余糖果数保留合法高位。效率保障仅遍历30 3030位二进制位每组数据常数级计算适配1e5组测试用例的规模。代码内容#includebits/stdc.husingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvt;typedefpairll,llpll;constll N1e610;constll mod1e97;constll INF1e18;ll a[40];intmain(){a[0]1;for(ll i1;i33;i)a[i]a[i-1]1;ll T;cinT;while(T--){ll ans0;ll m,n;cinmn;for(ll i33;i;i--){if(n*a[i]m)m-n*a[i],ansa[i];elseif(n*(a[i]-1)m)m-((m-n*(a[i]-1)-1)/a[i]1)*a[i];}if(nm)ans;coutansendl;}return0;}