codeforces 325B Stadium and Games

这道题思路很简单，设刚开始队伍数为d=2^p*x,其中x是奇数，则比赛场次n=(2^p-1)*x+(x-1)*x/2,然后从0开始枚举p的值，接着解一元二次方程x^2+(2^(p+1)-3)x-2*n=0，

易知此方程在0到10^9直接有且只有一个解。直接二分就行。

ps：这道题目数据很强，稍微有点错误就会出错。。。

#include<stdio.h>

#include<string.h>

#include<math.h>

#include<algorithm>

#define  LL long long

using namespace std;

LL n;

LL getans(LL a,LL b,LL s)

{

    LL mid,tmp;

    while(a<b)

    {

        mid=(a+b)/2;

        tmp=mid*mid-2*n+s*mid;

        if(tmp==0)

        {

           if(mid%2==0)//必须为奇数

              return -1;

           return mid;

        }

        else if(tmp>0)

           b=mid;

        else

           a=mid+1;

    }

    if(a*a-2*n+s*a==0&&(a&1))

       return a;

    return -1;

}

int main()

{

    LL i,j;

    while(scanf("%I64d",&n)==1)

	{

       LL tmp;

       LL cur=2,p,last=0;

       int flag=0;

       while(1)

       {

          if(cur-3<n*2)

          {

             tmp=sqrt(2*n+0.5);

             LL p=n*2/(cur-3);

             if(p>0&&p<tmp)tmp=p;//p必须大于零

             p=getans(0,tmp+3,cur-3);//这里刚开始时tmp+100，爆long long 了，TTT

             if(p>0&&last!=cur/2*p)

             {

               printf("%I64d\n",cur/2*p);

               flag=1;

               last=cur/2*p;

             }

          }

          else

             break;

          cur*=2;

       }

       if(!flag)printf("-1\n");

	}

    return 0;

}

巴特西

codeforces 325B Stadium and Games

最新文章

热门文章