首页 > 其他 > 详细

poj1067 取石子游戏

时间:2019-01-22 23:26:29      阅读:162      评论:0      收藏:0      [点我收藏+]

题目描述

题解:

数据范围这么大当然先打表了。

然后发现$P-position$分布极为稀疏。

不妨设$x<y$,则$P-position$为:$(0,0)$,$(1,2)$,$(3,5)$,$(4,7)$……

有两个规律:

1.所有正整数出现且仅出现一次。

2.第$k$个点的$y-x=k$。

所以有$Beatty$定理得:

1/a+1/b=1

a=b-1

得出一组解然后带通项就行了。

代码:

#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const double sq = sqrt(5);
const double K = (sq-1.0)/2.0;
const double D = (sq+1.0)/2.0;
const double G = (sq+3.0)/2.0;
int a,b,k;
int main()
{
    while(scanf("%d%d",&a,&b)>0)
    {
        int ans = 1;if(a>b)swap(a,b);
        for(int k = a*K-1;ans&&k<=(a+1)*K+1;k++)
            if(a==(int)(k*D)&&b==(int)(k*G))ans=0;
        printf("%d\n",ans);
    }
    return 0;
}

 

poj1067 取石子游戏

原文:https://www.cnblogs.com/LiGuanlin1124/p/10306480.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!