Bayan 2015 Contest Warm Up D題(GCD)

Bayan 2015 Contest Warm Up D題(GCD)

D. CGCDSSQ time limit per test 2 seconds memory limit per test 256 megabytes input standard input output standard output

Given a sequence of integers a1,?...,?an and q queries x1,?...,?xq on it. For each query xi you have to count the number of pairs (l,?r)such that 1?≤?l?≤?r?≤?n and gcd(al,?al?+?1,?...,?ar)?=?xi.

is a greatest common divisor of v1,?v2,?...,?vn, that is equal to a largest pZ喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vc2l0aXZlIGludGVnZXIgdGhhdCBkaXZpZGVzIGFsbCA8ZW0+djwvZW0+PGVtPmk8L2VtPi48L3A+CgoKCklucHV0CjxwPgpUaGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQgY29udGFpbnMgaW50ZWdlciA8ZW0+bjwvZW0+LCAoMT+h3D88ZW0+bjwvZW0+P6HcPzEwNSksCiBkZW5vdGluZyB0aGUgbGVuZ3RoIG9mIHRoZSBzZXF1ZW5jZS4gVGhlIG5leHQgbGluZSBjb250YWlucyA8ZW0+bjwvZW0+IHNwYWNlIHNlcGFyYXRlZCBpbnRlZ2VycyA8ZW0+YTwvZW0+MSw/Li4uLD88ZW0+YTwvZW0+PGVtPm48L2VtPiwKICgxP6HcPzxlbT5hPC9lbT48ZW0+aTwvZW0+P6HcPzEwOSkuPC9wPgo8cD4KVGhlIHRoaXJkIGxpbmUgb2YgdGhlIGlucHV0IGNvbnRhaW5zIGludGVnZXIgPGVtPnE8L2VtPiwgKDE/odw/PGVtPnE8L2VtPj+h3D8zP6HBPzEwNSksCiBkZW5vdGluZyB0aGUgbnVtYmVyIG9mIHF1ZXJpZXMuIFRoZW4gZm9sbG93cyA8ZW0+cTwvZW0+IGxpbmVzLCBlYWNoIGNvbnRhaW4gYW4gaW50ZWdlciA8ZW0+eDwvZW0+PGVtPmk8L2VtPiwKICgxP6HcPzxlbT54PC9lbT48ZW0+aTwvZW0+P6HcPzEwOSkuPC9wPgoKCgpPdXRwdXQKPHA+CkZvciBlYWNoIHF1ZXJ5IHByaW50IHRoZSByZXN1bHQgaW4gYSBzZXBhcmF0ZSBsaW5lLjwvcD4KCgoKU2FtcGxlIHRlc3QocykKCgoKaW5wdXQKPHByZSBjbGFzcz0="brush:java;">3 2 6 3 5 1 2 3 4 6 output

1
2
2
0
1

input

7
10 20 3 15 1000 60 16
10
1
2
3
4
5
6
10
20
60
1000

output

14
0
2
2
2
0
2
2
1
1

題意：給出n個數，然後給q個詢問，每次詢問給出一個x，問有多少個區間的GCD是x
思路：比賽的時候yy的一個做法
首先預處理出所有值的區間個數，這個用map存一下就好了，設為ans
然後再開兩個map 分別為mp mp2
mp存的是以Xi結尾的所有區間的GCD的數的個數
每次從Xi轉移到Xi+1，只需要累加以Xi結尾的區間的所有mp值與Xi+1的GCD的個數就好了，可以臨時賦給mp2，然後再賦給mp
按照這個方法從左往右for一遍就好了
然後查詢的時候直接在ans裡查就好了
復雜度大概是O(N*(每個數的因子個數))