首页 > 代码库 > 51nod1185(wythoff+高精度)

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 了啦。。。

 

代码:

 1 #include <bits/stdc++.h>
 2 #define ll long long
 3 #define geloutingyu 1000000000
 4 using namespace std;
 5 
 6 ll a[3]={618033988, 749894848, 204586834};
 7 
 8 int main(void){
 9     int t;
10     ll x, y;
11     scanf("%d", &t);
12     while(t--){
13         scanf("%lld%lld", &x, &y);
14         if(x>y){
15             swap(x, y);
16             }
17         ll cnt=y-x;
18         ll pre=cnt/geloutingyu, las=cnt%geloutingyu;
19         ll ans1=las*a[2];
20         ll ans2=pre*a[2]+las*a[1]+ans1/geloutingyu;
21         ll ans3=pre*a[1]+las*a[0]+ans2/geloutingyu;
22         ll gg=cnt+pre*a[0]+ans3/geloutingyu;
23         if(gg==x){
24             printf("B\n");
25         }else{
26             printf("A\n");
27         }
28     }
29     return 0;
30 }

 

51nod1185(wythoff+高精度)