【CF 914D】 Bash and a Tough Math Puzzle
原題連結：http://codeforces.com/problemset/problem/914/D
這題我在比賽當中想到詢問O((logn)^2)的作法，雖然壓常數後過了，可是最後還是被system test卡掉QQ
不過在賽後重送一次一模一樣的code卻過了，不知道是不是伺服器負荷量問題...
原題的詢問可以視為，詢問區間內無法被x整除的數字是否超過1個。
則考慮一個gcd線段樹，query的時候在外面開一個「無法被整除數字」的計數器。
函式裡，只要有區間能被x整除就直接return，否則就持續往詢問的區間遞迴。
如果當前node是涵蓋在詢問區間裡的：
case 1: l==r(node的區間只代表一個數字)
因為能遞迴到這裡表示一定不能整除，計數器+1
case 2: otherwise
暴力往下遞迴
最後在函式的開頭補上，計數器>1就直接return。
可以觀察到，會暴力遞迴到底的次數頂多只有兩次，兩次後計數器會>1，其他的待跑函式會全部return，複雜度O(logn)
總複雜度O(N+Qlogn)(不含修改，修改約O(logn*logC)，但gcd的期望值和單點修改的常數都遠比預計的小，所以可以不用在意)
這題我在比賽當中想到詢問O((logn)^2)的作法，雖然壓常數後過了，可是最後還是被system test卡掉QQ
不過在賽後重送一次一模一樣的code卻過了，不知道是不是伺服器負荷量問題...
原題的詢問可以視為，詢問區間內無法被x整除的數字是否超過1個。
則考慮一個gcd線段樹，query的時候在外面開一個「無法被整除數字」的計數器。
函式裡，只要有區間能被x整除就直接return，否則就持續往詢問的區間遞迴。
如果當前node是涵蓋在詢問區間裡的：
case 1: l==r(node的區間只代表一個數字)
因為能遞迴到這裡表示一定不能整除，計數器+1
case 2: otherwise
暴力往下遞迴
最後在函式的開頭補上，計數器>1就直接return。
可以觀察到，會暴力遞迴到底的次數頂多只有兩次，兩次後計數器會>1，其他的待跑函式會全部return，複雜度O(logn)
總複雜度O(N+Qlogn)(不含修改，修改約O(logn*logC)，但gcd的期望值和單點修改的常數都遠比預計的小，所以可以不用在意)
留言
張貼留言