Tag Discussion Solution Statistics Submit
 

RUPC 2013 (OUPC)
 

Sliding GCD

Time Limit : 1 sec, Memory Limit : 65536 KB

Sliding GCD

Problem Statement

自然数の集合 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\}) を求めよ.

Input

入力は以下の形式に従う.与えられる数は全て整数である.

N W

Constraints

  • 1 ≦ W ≦ N ≦ 10^5

Output

i = 1, 2, . . ., N-W+1 のときの f(\{i, i+1, . . ., i+W-1\}) の値を半角スペース区切りで 1 行に出力せよ.

Sample Input 1

10 2

Output for the Sample Input 1

2 3 3 3 3 3 3 3 3

GCD(\{1\}) = 1, GCD(\{2\}) = 2, GCD(\{1,2\}) = 1 となるから f(\{1,2\}) = 2 である.

Sample Input 2

30 7

Output for the Sample Input 2

7 8 9 10 10 11 11 11 11 12 11 12 10 12 12 11 10 12 12 12 10 11 11 13

Source: Ritsumeikan University Competitive Programming Camp 2013, Day2 , Problem set from Osaka University teams, Shiga, Japan, 2013-03-12
Problem Setter:  fura2