首页 > 代码库 > 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+高精度)