P1582 倒水，P2158 [SDOI2008]仪仗队——数学，二进制

有n个瓶子，里面都有一升水，但是只想保留k个瓶子，只能两个瓶子里面的水体积相等时才能倒在一个瓶子里；不能丢弃有水的瓶子；瓶子容量无限；

问需要购买几个额外的瓶子才能满足条件；

因为每个瓶子一开始只有一升水，那么合并后每个瓶子里面的水体积都是2,也就是说，n个瓶子最少能合并成n的二进制数中1的个数个瓶子；

那么我们要买多少个瓶子呢？面对一个二进制数，我们因为要让他的1的个数变小，我们要加上lowbit （x&(-x)），这个表示的是保留这个数从右边起第一个1的位置，

比如：100010 lowbit是10

111111110                     10

111111111                        1

1000001000                  1000；

这样我们就可以进位，而且1的个数不会增多，当有连续的1时，我们的1的个数就降了下来，等到<=k时退出循环即可；

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

int n,k;

int ans;

int work(int x)

{

    int num=;

    for(;x;x-=x&(-x)) num++;

    return num;

}

int main()

{

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

    while(work(n)>k)

    {

        ans+=n&(-n);

        n+=n&(-n);

    }

    printf("%d",ans);

    return ;

}

P2158 [SDOI2008]仪仗队

方阵中，你在左下角，求看不见的人数；

可以知道我们只能看到横纵坐标gcd等于1（互质）的，当然(2,2)要特判；

我们只需要求右下角的三角形，然后*2+1就好了。（加1是（2,2））；

根据坐标，求（x,y）比y小的数中有几个和y互质

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=;

int n;

int p[maxn];

int ans;

int main()

{

    scanf("%d",&n);

    if(n==)

    {

        printf("");

        return ;

    }

    for(int i=;i<=n;i++)

    {

        p[i]=i;

    }

    for(int i=;i<=n;i++)

    {

        if(p[i]==i)

        {

            for(int j=i;j<=n;j+=i)

            {

                p[j]=p[j]*(i-)/i;//欧拉函数

            }

        }

    }

    for(int i=;i<n;i++) ans+=p[i];

    printf("%d",ans*+);

    return ;

}