nowcoder 牛客小白月赛81

發表於 更新於 分類於 Disqus： 文章字數： 452 所需閱讀時間 ≈ 2 分鐘
F(gcd性质优化)

https://ac.nowcoder.com/acm/contest/69791

F - 小辰刚学 gcd

https://ac.nowcoder.com/acm/contest/69791/F

长度n数组a

m个询问, 每次求query(l,r) = 集合{gcd(a[i..r]),i=l..r}的大小

范围

n 6e5

$a_i \in [1,2^{31}]$

1s

256MB

我的思路

显然 集合中的数 一定是 a[r] 的 因子，且两两互为倍数

所以 最多32个

然后我糊了一个st表+幂次查询，应该是 $O((n+m)\log(a_i)\log(n))$

TLE了

https://ac.nowcoder.com/acm/contest/view-submission?submissionId=65524654

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define per(i, a, b) for (int i = (b); (i--) > (a);)
int readint() { int v; scanf("%d", &v); return v; }
int gcd(int a, int b) { while (b != 0) { int tmp = a % b; a = b; b = tmp; } return a; }
const int PWR = 21;
int lrg[600010][PWR];  // l..r gcd
int main() {
  int n = readint();
  int m = readint();
  rep(i, 1, n + 1) lrg[i][0] = readint();
  rep(pwr, 1, PWR) {
    // i..(i+(1<<pwr)-1)
    int hstep = 1 << (pwr - 1);  // half step
    rep(i, 1, n + 1) {
      lrg[i][pwr] = lrg[i][pwr - 1];
      if (i + hstep <= n) {
        lrg[i][pwr] = gcd(lrg[i][pwr], lrg[i + hstep][pwr - 1]);
      }
    }
  }
  rep(i, 0, m) { // O(m *
    int l = readint();
    int r = readint();
    int ans = 1;
    int res = lrg[r][0];
    while (r >= l) { // O(log(a_i) *
      per(pwr, 0, PWR) { // O(log(n) *
        int pos = r - (1 << pwr) + 1;
        if (pos < l)
          continue;
        // gcd( gcd[r-(1<<pwr)+1....r], res)
        // int g = gcd(lrg[pos][pwr], res);
        // if (g != res)
        //   continue;
        if (lrg[pos][pwr] % res != 0)
          continue;

        // 最大2的倍数长度 且 gcd(gcd[pos..r],res) == res
        r = pos - 1;
        if (pos == l)
          break;
        // O( *log(a_i) )
        int newres = gcd(lrg[r][pwr], res);  // [pwr]长度,少算很多轮?
        ans += newres != res;
        res = newres;
        break;
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}

题解

我的问题是，在查询的代价其实是 $O(m (\log(a_i))^2\log(n))$

而这里 [...r]对集合个数 做出贡献的左侧 pos, 在 [...r-1]中一定存在

所以, 这样转移可以，让查询变成直接只查询 上一个位置中出现过的左侧点