sgu-255 Winsock 3 Beta - c++编程基础

题目大意：

给定一个函数 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; }