自然数の集合 S に対して,集合 \{ GCD(T) | T ⊆ S, T は空でない \} の要素数を f(S) とおく.
ここで,GCD(T) は T に含まれるすべての数を割り切るような最大の整数である.
特に,T が一つの整数 a のみからなるときは GCD(\{a\}) = a であることに注意せよ.
i = 1, 2, . . ., N - W+1 に対して f(\{i, i+1, . . ., i+W - 1\}) を求めよ.
入力は以下の形式に従う.与えられる数は全て整数である.
N W
i = 1, 2, . . ., N-W+1 のときの f(\{i, i+1, . . ., i+W-1\}) の値を半角スペース区切りで 1 行に出力せよ.
10 2
2 3 3 3 3 3 3 3 3
GCD(\{1\}) = 1, GCD(\{2\}) = 2, GCD(\{1,2\}) = 1 となるから f(\{1,2\}) = 2 である.
30 7
7 8 9 10 10 11 11 11 11 12 11 12 10 12 12 11 10 12 12 12 10 11 11 13