前から見ていくと、TさんもAさんもどう行動すれば最適か、見通しを立てにくい。
後ろから見ていくとよい。
初期値は DP[N][0]= True、それ以外はFalse。
最終的に DP[0][0]= TrueならTさんの勝ち。
遷移を考える。
i k : 0 1 2 3 4 5 6 159 .... 23 5 DP[i][k]: o x o o x o x
この状態の時、DP[i−1] を求めたい。
j=0～6 について1つずつ調べる。j を固定すると、i ターン目の操作を加えた時のあまりは2通り。
Si=5 のとき、 i-1ターン目までで作られた T を7で割ったあまりがたとえば 3 なら、 i ターン目までで作られる T を7で割ったあまりは以下のいずれか。 Siを使わないと 30 % 7 = 2 Siを使うと 35 % 7 = 0
これが、Tさんが勝つ状態になっているかどうかで、DP[i−1][j] を求められる。
Tさんは自分が勝てる方を選べばよいので、遷移先のどれか1つがTrueなら十分。
AさんはTさんが勝ってしまうのを避けるので、避けられない（＝遷移先が全てTrueの）状態でないといけない。
Si=5 k : 0 1 2 3 4 5 6
DP[i][k]: o x o o x o x のとき
Xi=Tの時 Xi=Aの時
j k DP[i][k] DP[i-1][j] DP[i-1][j]
0 → 0, 5 o, o o o
1 → 3, 1 o, x o x
2 → 6, 4 x, x x x
3 → 2, 0 o, o o o
4 → 5, 3 o, o o o
5 → 1, 6 x, x x x
6 → 4, 2 x, o x x
これでDPを計算していけばよい。
2つの数が互いに素というのは、i=23⋅72⋅11,j=32⋅5 のように、各整数を素因数分解したときに同じ素因数が出てこないということ。
指数部分は重要でないので捨てて、i={2,7,11},j={3,5} のように、各整数の素因数の集合を事前計算しておく。
次に、B−A≤72 という変わった制約に注目する。
73 以上の素因数は元の整数集合に2つ以上出てこず、明らかに被らないので、考える必要が無い。
事前計算で調べるのは 71 までの素因数だけでよく、その個数はちょうど 20 個となる。
ただし S は既述の通り 71 まで。つまり 220≃106 程度の状態数で済む。i の範囲も73個が上限なので、S をbitフラグなどで表現しておけば十分間に合う。
初期状態は DP[0][0]=1。答えは ∑SDP[B−A+1][S]。
遷移は、i 番目の整数に含まれる素数集合のbitフラグを pi として、各 0≤s<220 に対し
とすればよい。