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=0;
    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 0;
}

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=40010;
int n;
int p[maxn];
int ans;
int main()
{
    scanf("%d",&n);
    if(n==1)
    {
        printf("0");
        return 0;
    }
    for(int i=1;i<=n;i++)
    {
        p[i]=i;
    }
    for(int i=2;i<=n;i++)
    {
        if(p[i]==i)
        {
            for(int j=i;j<=n;j+=i)
            {
                p[j]=p[j]*(i-1)/i;//欧拉函数
            }
        }
    }
    for(int i=1;i<n;i++) ans+=p[i];
    printf("%d",ans*2+1);
    return 0;
}