Codeforce 168E Wizards and Numbers

煩人數學題。。。
本來直接用NP算他，結果TLE + +
首先，先用 dfs( b, a%b ) 算一下，看會不會贏，
如果dfs( b, a%b )會輸，那就代表這個壯況會贏
如果dfs( b, a%b )會贏，那就知道弄成那個狀況的人就贏了
如果希望自己贏，那麼走的步數必定要是偶數。
a = q*b + a%b;
將 q 轉為 y1*（b^x1） + y2*（b^x2） + y3*（b ^x3） + ... + yn
若 sumof( yi ) 是偶數，則先手贏
若 sumof( yi ) 是奇數，則後手贏

如果 b 是奇數，就輕鬆了，
若含b的多項式係數和是偶數，yn是偶數，那麼 q 為偶數。-> 2 | sumof( yi )
若含b的多項式係數和是奇數，yn是奇數，那麼 q 為偶數。-> 2 | sumof( yi )
若含b的多項式係數和是偶數，yn是奇數，那麼 q 為奇數。-> sumof( yi ) %2 != 0
若含b的多項式係數和是奇數，yn是奇數，那麼 q 為奇數。-> sumof( yi ) %2 != 0
其實很好證，若q是偶數，不是奇（係數和%2=1）加奇，就是偶（係數和%2=0）加偶

但如果 b 是偶數，就麻煩了，
所以就把b改成奇數（OoO）也就是改成 (b+1)（怕改太多會壞掉）
將 q 轉為 z1*（ (b+1)^x1 ） + z2*（ (b+1)^x2 ） + z3*（ (b+1) ^x3 ） + ... + zn
若且為若含b+1的多項式係數和是偶數，zn是偶數，那麼 q 為偶數。
若且為若含b+1的多項式係數和是奇數，zn是奇數，那麼 q 為偶數。
若且為若含b+1的多項式係數和是偶數，zn是奇數，那麼 q 為奇數。
若且為若含b+1的多項式係數和是奇數，zn是偶數，那麼 q 為奇數。
但要怎麼推出 sumof( yi ) 呢？
其實重點只在於 zn，因為前面的係數和一定是偶數（b+1的任意次方係數和為偶數）。

http://codepad.org/EvH8mbUS