51nod1185(wythoff+高精度)

题目链接:https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1185

题意:中文题诶~

思路:wythoff模板题,和51nod1072基本一样(http://www.cnblogs.com/geloutingyu/p/6198094.html),不过本题的数据比较大(1e18),会有精度问题;

我们可以:

令:cnt=abs(x-y);

  geloutingyu=1e9;

  a[3]={618033988, 749894848, 204586834} ((sqrt(5)+1)/2=1.618033988749894848204586834, 我们可以先不计算1, 最后加上一个cnt就好了);

  pre=cnt/geloutingyu------1;

  las=cnt%geloutingyu-----2;

  gg=cnt+cnt*a[0]/geloutingyu+cnt*a[1]/mod/mod+cnt*a[2]/mod/mod/mod-----3;

  联立1, 2 即有 cnt=pre*geloutingyu+las------4;

  再将4带入到3中,有:

  gg=cnt+pre*a[0]+las*a[0]/mod+pre*a[1]/mod+las*a[1]/mod/mod+pre*a[2]/mod/mod+las*a[2]/mod/mod/mod----5;

  我们再令:ans1=las*a[2], 则有:

   gg=cnt+pre*a[0]+las*a[0]/mod+pre*a[1]/mod+las*a[1]/mod/mod+pre*a[2]/mod/mod+(ans1)/mod/mod/mod;

  我们再令:ans2=las*a[1]+pre*a[2]+ans1/mod, 则有:

   gg=cnt+pre*a[0]+las*a[0]/mod+pre*a[1]/mod+(ans2)/mod/mod;

  我们再令:ans3=las*a[0]+pre*a[1]+ans2/mod, 则有:

  gg=cnt+pre*a[0]+(ans3)/mod;

所以我们只要依次求出ans1, ans2, ans3 就能解出 gg 了啦。。。

代码:

 #include <bits/stdc++.h>
#define ll long long
#define geloutingyu 1000000000
using namespace std; ll a[]={, , }; int main(void){
int t;
ll x, y;
scanf("%d", &t);
while(t--){
scanf("%lld%lld", &x, &y);
if(x>y){
swap(x, y);
}
ll cnt=y-x;
ll pre=cnt/geloutingyu, las=cnt%geloutingyu;
ll ans1=las*a[];
ll ans2=pre*a[]+las*a[]+ans1/geloutingyu;
ll ans3=pre*a[]+las*a[]+ans2/geloutingyu;
ll gg=cnt+pre*a[]+ans3/geloutingyu;
if(gg==x){
printf("B\n");
}else{
printf("A\n");
}
}
return ;
}
上一篇:Git 经常使用命令合集


下一篇:【LG3245】[HNOI2016]大数