1282 . 愛蜜利雅的作業2

1282 . 愛蜜利雅的作業2

題意:
給定一數列$A$，兩種操作，一是區間加值，二是求區間最大公因數。

solve:
因為輾轉相除法的特性，$gcd(a, b, c, d...) = gcd(a, b - a, c - b, d - c...)$，所以可以構造一個數列$g_i = A_i - A_{i - 1}$。
這樣就可以維護線段樹了。

操作1:
用BIT維護區間加值，然後因為我們線段樹維護的是數列差，所以區間加可以變成單點加。

操作2:
求$gcd(A_{[l, r]})$的時候，是要求$gcd(A_l, gcd(A_{[l + 1, r]}))$，原因顯而易見。

#我自己做的出來 (ﾉ>ω<)ﾉ

code: