1         for(int i = 1; i <= n; ++i) { 2             int x = a[i], y = i; 3             for(int j = 0; j < ans[i - 1].size(); ++j) { 4                 int gcd = GCD(x, ans[i - 1][j].first); 5                 if(gcd != x) { 6                     ans[i].push_back(make_pair(x, y)); 7                     x = gcd, y = ans[i - 1][j].second; 8                 } 9             }10             ans[i].push_back(make_pair(x, y));11         }

 1 //#pragma comment(linker, "/STACK:102400000, 102400000") 2 #include <algorithm> 3 #include <iostream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <ctime>10 #include <list>11 #include <set>12 #include <map>13 using namespace std;14 typedef long long LL;15 typedef pair <int, int> P;16 const int N = 1e6 + 5;17 int a[N/10 + 5], bit[N], _pos[N]; //_pos存的是gcd上一次出现的位置18 vector <P> ans[N/10 + 5]; //存的是以i为右端点的gcd19 struct query {20     int l, r, pos;21     bool operator <(const query& cmp) const {22         return r < cmp.r;23     }24 }q[N/10 + 5];25 int res[N/10 + 5]; //答案26 27 void init(int n) {28     memset(_pos, 0, sizeof(_pos));29     memset(bit, 0, sizeof(bit));30     for(int i = 1; i <= n; ++i) {31         ans[i].clear();32     }33 }34 35 int GCD(int a, int b) {36     return b ? GCD(b, a % b): a;37 }38 39 void add(int i, int x) {40     for( ; i <= N; i += (i&-i))41         bit[i] += x;42 }43 44 int sum(int i) {45     int s = 0;46     for( ; i >= 1; i -= (i&-i))47         s += bit[i];48     return s;49 }50 51 int main()52 {53     int n, m;54     while(scanf("%d %d", &n, &m) != EOF) {55         init(n);56         for(int i = 1; i <= n; ++i) {57             scanf("%d", a + i);58         }59         for(int i = 1; i <= m; ++i) {60             scanf("%d %d", &q[i].l, &q[i].r);61             q[i].pos = i;62         }63         for(int i = 1; i <= n; ++i) {64             int x = a[i], y = i;65             for(int j = 0; j < ans[i - 1].size(); ++j) {66                 int gcd = GCD(x, ans[i - 1][j].first);67                 if(gcd != x) {68                     ans[i].push_back(make_pair(x, y));69                     x = gcd, y = ans[i - 1][j].second;70                 }71             }72             ans[i].push_back(make_pair(x, y));73         }74         sort(q + 1, q + m + 1);75         int p = 1;76         for(int i = 1; i <= n; ++i) {77             for(int j = 0; j < ans[i].size(); ++j) {78                 if(!_pos[ans[i][j].first]) {79                     add(ans[i][j].second, 1);80                     _pos[ans[i][j].first] = ans[i][j].second;81                 } else {82                     add(_pos[ans[i][j].first], -1);83                     _pos[ans[i][j].first] = ans[i][j].second;84                     add(ans[i][j].second, 1);85                 }86             }87             while(i == q[p].r && p <= m) {88                 res[q[p].pos] = sum(q[p].r) - sum(q[p].l - 1);89                 ++p;90             }91         }92         for(int i = 1; i <= m; ++i) {93             printf("%d\n", res[i]);94         }95     }96     return 0;97 }