Educational Codeforces Round 24 E. Card Game Again 二分+线段树

链接：

http://codeforces.com/contest/818/problem/E

题意：

给你n个数，问有多少个子串的乘积模k等于0

题解：

我们先用线段树保存每一段的乘积%k

然后枚举每一个位置i，二分找到最后一个pos，使得从pos到i之间的乘积能被k整除

这样从1到pos之间任意一个位置到i都能被k整除即ans+=pos

注意建树的时候要先对Tree[rt]做一次取模，不然会wa

代码：

31 ll n, k;
32 ll a[MAXN];
33 ll Tree[MAXN << 2];
34 
35 void build(ll l, ll r, ll rt) {
36     if (l == r) {
37         cin >> Tree[rt];
38         Tree[rt] %= k;
39         return;
40     }
41     ll m = (l + r) >> 1;
42     build(lson);
43     build(rson);
44     Tree[rt] = Tree[rt << 1] * Tree[rt << 1 | 1] % k;
45 }
46 
47 ll query(ll L, ll R, ll l, ll r, ll rt) {
48     if (L <= l && r <= R) return Tree[rt];
49     ll ret = 1;
50     ll m = (l + r) >> 1;
51     if (L <= m) ret = ret*query(L, R, lson) % k;
52     if (R > m) ret = ret*query(L, R, rson) % k;
53     return ret;
54 }
55 
56 int main() {
57     ios::sync_with_stdio(false), cin.tie(0);
58     cin >> n >> k;
59     build(1, n, 1);
60     ll ans = 0;
61     rep(i, 1, n + 1) {
62         ll l = 1, r = i, pos = 0;
63         while (l <= r) {
64             ll m = (l + r) >> 1;
65             if (query(m, i, 1, n, 1) == 0) l = m + 1, pos = m;
66             else r = m - 1;
67         }
68         ans += pos;
69     }
70     cout << ans << endl;
71     return 0;
72 }