CF 256C Furlo and Rublo and Game

暴力的求SG函數會超時，正解是先處理出10^6以內的SG值，對於更大的，開根號之後計算出。

小數據觀察可以發現sg函數值成段出現，而且增長速度很快，因此可以計算出來每一段的范圍，只需打表即可。

Nim游戲：

Nim和：L.Bouton給出了一個定理，狀態(X1, X2, ..., Xn)為必敗態當且僅當X1 xor X2 xor .... xor Xn = 0，xor是二進制的按位異或操作。

#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
ll x, a[] = {3, 15, 81, 6723, 50625, 2562991875LL};
int sg[] = {0, 1, 2, 0, 3, 1, 2}, n, ans = 0;

int main() {

    cin >> n;
    while (n--) {
        cin >> x;
        ans ^= sg[lower_bound(a, a+6, x)-a];
    }
    cout << (ans ? "Furlo" : "Rublo") << endl;

    return 0;
}