1 #include <cstdio>  2 #include <cstring>  3 #include <algorithm>  4 #include <vector>  5 //#include <cmath>  6   7 using namespace std;  8 #define lson rt<<1, l, mid  9 #define rson rt<<1|1, mid+1, r 10 typedef pair<int, int> PII; 11 //typedef __int64 lld; 12 typedef long long lld; 13 const int MAXN = 100005; 14  15 struct Q { 16     int l, r, id; 17     Q() {} 18     Q(int a, int b, int c):l(a), r(b), id(c) {} 19     bool operator < (const Q& cmp) const { 20         return l > cmp.l; 21     } 22 }; 23 vector<Q> GS[55]; 24 int a[MAXN]; 25 lld sum[MAXN << 2]; 26 lld add[MAXN << 2]; 27 int n, m, q; 28 lld out[MAXN]; 29 int log2[MAXN]; 30  31 struct RMQ { 32     int a[MAXN][22]; 33     void init(int A[], int N) { 34         for (int i = 1; i <= N; i++) a[i][0] = A[i]; 35         for (int j = 1; (1 << j) <= N; j++) { 36             for (int i = 1; i + j - 1 <= N; i++) { 37                 a[i][j] = __gcd(a[i][j-1], a[i + (1<<(j-1))][j - 1]); 38             } 39         } 40     } 41     int rmq(int L, int R) { 42       //  if (R < L) while (1); 43         if (R < L) return 0; 44         int k = log2[R - L + 1]; 45         return __gcd(a[L][k], a[R-(1<<k)+1][k]); 46     } 47 }AC; 48  49 /*     *segment tree*    */ 50 void build() { 51     memset(add, 0, sizeof(add)); 52     memset(sum, 0, sizeof(sum)); 53 } 54 void Down(int rt, int l, int r) { 55     if (add[rt]) { 56         int mid = r + l >> 1; 57         add[rt<<1] += add[rt]; 58         add[rt<<1|1] += add[rt]; 59         sum[rt<<1] += (lld)(mid - l + 1) * add[rt]; 60         sum[rt<<1|1] += (lld)(r - mid) * add[rt]; 61         add[rt] = 0; 62     } 63     return ; 64 } 65 void Up(int rt) { 66     sum[rt] = sum[rt<<1] + sum[rt<<1|1]; 67 } 68 void update(int rt, int l, int r, int L, int R) { 69     if (L > R) return ; 70     if (l >= L && r <= R) { 71         add[rt] += 1; 72         sum[rt] += r - l + 1; 73         return ; 74     } 75     Down(rt, l, r); 76     int mid = r + l >> 1; 77     if (mid >= L) update(lson, L, R); 78     if (R > mid) update(rson, L, R); 79     Up(rt); 80 } 81 lld query(int rt, int l, int r, int L, int R) { 82     if (L > R) return 0LL; 83     if (l >= L && r <= R) { 84         return sum[rt]; 85     } 86     Down(rt, l, r); 87     int mid = r + l >> 1; 88     lld ret = 0; 89     if (mid >= L) ret += query(lson, L, R); 90     if (R > mid) ret += query(rson, L, R); 91     return ret; 92 } 93 /*     *segment tree*    */ 94  95 PII arr[MAXN]; 96 void solve(vector<Q> vec, int M) { 97     sort(vec.begin(), vec.end()); 98     build(); 99     int l = 1, r = 1;100     for (int i = 1; i <= n; i++) {101         if (a[i] % M != 0 || AC.rmq(i, n) % M == 0 && AC.rmq(i, n) > M) {102             arr[i] = make_pair(-1, -1);103         }else {104             l = max(l, i); //r = max(r, i);105             while (l <= n && AC.rmq(i, l) % M == 0 && AC.rmq(i, l) > M) ++ l;106             r = max(l, r);107             while (r+1 <= n && AC.rmq(i, r+1) == M) ++ r;108             if (AC.rmq(i, l) == M) {109                 arr[i] = make_pair(l, r);110             }else {111                 arr[i] = make_pair(-1, -1);112             }113         }114     }115     int now = n, siz = vec.size();116     for (int i = 0; i < siz; i++) {117         Q e = vec[i];118         while (now >= 1 && e.l <= now) {119             if (arr[now].first != -1) {120                 update(1, 1, n, max(1, arr[now].first), arr[now].second);121             }122             -- now;123         }124         out[e.id] = query(1, 1, n, e.l, e.r);125     }126 }127 /*128 129 4 4 4130 1 2 3 4131 1 2 3 4132 0 4 1133 0 4 2134 0 4 3135 0 4 4136 137 4 4 4138 1 2 3 4139 1 2 3 4140 0 4 1141 0 4 2142 0 2 1143 3 4 4144 145 */146 147 int gs[55];148 int main() {149     for (int i = 0; i < MAXN; i++) {150         log2[i] = (i == 0 ? -1 : log2[i >> 1] + 1);151     }152     while (scanf("%d%d%d", &n, &m, &q) == 3) {153         for (int i = 1; i <= n; i++) scanf("%d", &a[i]);154         AC.init(a, n);155         for (int i = 0; i < m; i++) scanf("%d", &gs[i]);156         sort(gs, gs + m);157         for (int i = 0; i < m; i++) GS[i].clear();158         for (int i = 1; i <= q; i++) {159             int l, r, x;160             scanf("%d%d%d", &l, &r, &x);161             x = lower_bound(gs, gs + m, x) - gs;162             GS[x].push_back(Q(l + 1, r, i));163         }164         for (int i = 0; i < m; i++) {165             solve(GS[i], gs[i]);166         }167         for (int i = 1; i <= q; i++) printf("%lld\n", out[i]);168     }169     return 0;170 }