首页 > 代码库 > 51nod 1185 威佐夫游戏 V2

51nod 1185 威佐夫游戏 V2

思路:

威佐夫博弈 + 乘法模拟。

实现:

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 typedef long long ll;
 5 
 6 const ll tmp[3] = { 618033988, 749894848, 204586834 };
 7 const ll mod = 1e9;
 8 
 9 int main()
10 {
11     int t;
12     ll a, b;
13     cin >> t;
14     while (t--)
15     {
16         cin >> a >> b;
17         if (a < b)
18             swap(a, b);
19         ll x = a - b;
20         ll c = a - b;
21         ll p = c / mod, l = c % mod;
22         ll a1 = l * tmp[2];
23         ll a2 = p * tmp[2] + l * tmp[1] + a1 / mod;
24         ll a3 = p * tmp[1] + l * tmp[0] + a2 / mod;
25         ll a4 = c + p * tmp[0] + a3 / mod;
26         cout << (a4 == b ? B : A) << endl;
27     }
28     return 0;
29 }

 

51nod 1185 威佐夫游戏 V2