ACM集训题

Let me alone.

---

题目
gcd变化次数， https://ac.nowcoder.com/acm/contest/69791/F
线段树二分， 理解01排序，https://www.luogu.com.cn/problem/P2824
2023ccpc桂林C， 线性基， https://codeforces.com/gym/104768/problem/C
https://ac.nowcoder.com/acm/contest/95323/K
基环树 https://www.luogu.com.cn/problem/P1399
2023ccpc桂林I https://codeforces.com/gym/104768/problem/I
2023ccpc桂林H https://codeforces.com/gym/104768/problem/H
2023icpc桂林J https://codeforces.com/gym/104768/problem/J
牛客 基础算法班

GCD 的变化次数

注意到的性质：gcd(x, y) <= min(x,y) → gcd(x,y) <= x / 2

相当于 GCD 要不不变，要不变小 1/2 O(log(n))

• 对于一个子序列的 最大公约数（GCD），可以认定这个 最大公约数的 可能性是可以枚举的。

  #include<bits/stdc++.h>
  using namespace std;
  #define int long long
  const int N = 6e5 + 10;
  vector<pair<int, int>> pos[N];
  void build(vector<int>& a){
      int n = a.size() - 1;
      pos[1].push_back({1,a[1]});
      for(int i = 2; i <= n; i++){
          pos[i].push_back({i,a[i]});
          int t = a[i];
          for(auto [x,y] : pos[i - 1]){
              int now = gcd(t,y);
              if(t != now){
                  pos[i].push_back({x,now});
                  t = now;
              }
          }
      }
  }
  signed main(){
      ios::sync_with_stdio(false);
      cin.tie(0);
      cout.tie(0);
      int n, m;
      cin >> n >> m;
      vector<int> a(n + 1);
      for(int i = 1; i <= n; i++) cin >> a[i];
      build(a);
  	while(m --){
  		int l, r;
  		cin >> l >> r;
          int ans = 0;
          for(auto [x,y]: pos[r]){
              if(x >= l){
                  ans += 1;
              }else break;
          }
  		cout << ans << "\n";
  	}
  }