题目：

　　Recently, Peter saw the equation x0+2x1+4x2+...+2mxm=nx0+2x1+4x2+...+2mxm=n. He wants to find a solution (x0,x1,x2,...,xm)(x0,x1,x2,...,xm) in such a manner that ∑i=0mxi∑i=0mxi is minimum and every xixi (0≤i≤m0≤i≤m) is non-negative.

Input　

　　There are multiple test cases. The first line of input contains an integer TT (1≤T≤105)(1≤T≤105), indicating the number of test cases. For each test case:

　　The first contains two integers nn and mm (0≤n,m≤109)(0≤n,m≤109).

Output

　　For each test case, output the minimum value of ∑i=0mxi∑i=0mxi.

　
Sample Input

Sample Output

题意：

　　给你一个方程：x0+2x1+4x2+...+2^mxm=n，找一组非负的解，使得x0+x1+...+xm最小。能不能有小数呢？题目没说。。。但是根据样例可以发现，是不会有小数的。

分析：

　　我们想一想如果想要x的和最小，那肯定要让系数大的x最大，所以解就是：n/2^m。但是，我也不知道为啥它就不能有小数，这可能是题意不明，我们就把xi属于N当成条件就好了。既然这样，n/2^m不一定是小数，那么直接计算就不行了，但是总体的思路没有变，要x前面系数大的x大。然后，我们就考虑把n拆成二进制，于是每一位对应一个x，我们把m+1位及以上的数都加到xm身上，剩下的哪一位有数加在哪就好了，问题直接解决。

代码

#include <cstdio>

int main(){

    int t;

    scanf("%d",&t);

    for(int jsjs=;jsjs<=t;jsjs++){

        int n,m;

        scanf("%d%d",&n,&m);

        int ans=;

        for(int i=;i<=m&&n;i++){//m可能很大，防止t掉

            ans+=(n&);

            n>>=;

        }

        ans+=n;

        printf("%d\n",ans);

    }

    return ;

}

巴特西

Aaronson,又是思维题

题目：

Input

Output

Sample Input

Sample Output

题意：

分析：

代码

最新文章

热门文章