sgu-255 Winsock 3 Beta

sgu-255 Winsock 3 Beta

題目大意：

給定一個函數f(x)=g(x+1)+g(x+2)+.....+g(x?2)，其中g(x)=[x的二進制表示有且僅有3個1]。給你N(N<=100)個輸入，每個輸入給你一個m(m<=231?1)，要你求出f(x)=m是否存在唯一的整數解，存在輸出YES，否則輸出NO。

解題思路：

首先我們考慮函數f(x)的單調性，f(x+1)?f(x)=g(x?2+2)+g(x?2+1)?g(x+1)，從g(x)的定以來看，那麼有：g(x)=g(x?2)。所以f(x+1)?f(x)=g(x?2+1)，所以我們可以發現f(x)是單調不降的。那麼如果f(x0)=m是有唯一解得話，那麼就要滿足f(x0+1)?f(x0)=1,f(x0)?f(x0?1)=1?g(x0?2+1)=g(x0?2?1)=1。然後我們觀察發現，滿足g(x0?2?1)=1必須有x0二進制下最後一定是.....10，發現這同時也滿足g(x0?2+1)=1。
所以x0=2t+2+2(t>=0)，然後我們分類討論一下發現f(2t+2+2)=(t+22)+1，所以我們要做的就是對於f(2t+2+2)=(t+22)+1=m是否有非負整數解。
這很好做，再次不再贅述。

AC代碼：

#include 
#include 
#include 
#include 
#include 
#include 
#define sqr(a) ((a)*(a))

using namespace std;

const double eps=1e-8;

int n;

int main()
{
    scanf("%d",&n);
    for(;n>0;n--)
    {
        long long m;
        scanf("%lld",&m);
        if(m<=1)
        {
            puts("NO");
            continue;
        }
        long long a=1,b=3,c=-2*m+4;
        long long delta=sqr(b)-4*a*c;
        long long haha=(long long)(sqrt(delta)+eps);
        if(sqr(haha)==delta)
            puts("YES");
        else puts("NO");
    }
    return 0;
}