CodeForces #Bayan2015 : D. CGCDSSQ
問題
大きさ n の整数配列が与えられる。
その後 q 回、クエリxが投げられる。
各クエリごとに、区間の gcd が x となるような候補がいくつあるか答えよ。
解法
nが大きいためとなるような区間の全探索をすることはできない。
解法の一つとして、要素を一つ加えた時に候補となるgcdとその数を保持するMapを作り
動的計画法のようなアイデアで、区間を１つずつ増やしながらそれまでの区間で存在しうるgcdと
加えた区間の要素のgcdを取り、新たなgcdのMapを作る。
例えば、以下のような配列ではMapは次のように動く。
10 20 3
Map := 存在するgcdとその数を保持する
i = 0 Map: {10 = 1}
i = 1 Map: {10 = 1, 20 = 1}
3を区間に加える -> gcdMapの各keyと3のgcdを取り新たなMapを作る
となるため、次のMapは以下のようになる。
i = 2 Map: {1 = 2, 3 = 1}
n回のループを回す過程で、Mapのkeyの個数分だけgcdを取る処理行われる。
保持するkeyの数の最大値を考えてみると、Mapに保持されている数と素にならないような
かつ単調増加となるように数を追加していけばkeyがリセットされず残り続ける事が分かる。
その最大値はを超えない2のべき乗の数 = 高々30個
1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, ..., 536870912
よって全体の計算量はとなる。
