题目地址：http://codeforces.com/contest/474/problem/F
由题意可知，最后可以留下来的一定是区间最小gcd。那就转化成了该区间内与区间最小gcd数相等的个数。区间最小gcd一定小于等于区间最小值，所以只要求最小值的个数。然后用r-l+1-个数即可。
对于以上信息，可以用线段树来维护。分别维护区间gcd，区间最小值以及区间最小值的个数。
代码如下：
#include #include #include #include #include #include #include #include #include
