题解 | #小辰打比赛#

欢迎关注

珂朵莉 牛客周赛专栏

珂朵莉 牛客小白月赛专栏

F. 小辰刚学 gcd

我多么想，出题人，你可以亚撒西一点。

关于大量区间查询问题，还有gcd,最值，位运算这类，往往可以借助ST来加速。

这题比较特殊，可以分治二分（不知道这样说法对不对）来快速计算整个区间的不同gcd数。

可惜这个思路TLE了，感觉被严格卡复杂度了，多一个log也不行。

Java卡在56%， 等价C++（常数优化后）卡90%。

其实正解的思路，在数组 按与/或操作，区间查询最值等等问题，经常有出现。

就是维护变动的点列表

位运算的话，最多32位，所以最多32个点

而gcd的话，其实也是一样，因为最小的质因子为2， 而2^32是最大的整数

而arr[i + 1]变动点的列表，可以基于arr[j]的基础上，生成。

因此整个是时间复杂度为 O(32n)

贴一个chatgpt翻译后的c++代码

原一模一样的java代码被卡在70%, 数据还是卡常了。

#include <iostream>  
#include <vector>  
#include <algorithm>  
#include <cmath>  
  
using namespace std;  
  
long gcd(long a, long b) {  
    return b == 0 ? a : gcd(b, a % b);  
}  
  
int main() {  
    
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    int n, q;  
    cin >> n >> q;  
    vector<long> arr(n);  
    vector<vector<pair<long, int>>> g(n);  
    for (int i = 0; i < n; i++) {  
        cin >> arr[i];  
        long v = arr[i];  
        g[i].push_back({v, i});  
        if (i > 0) {  
            auto& prev = g[i - 1];  
            for (auto& pair : prev) {  
                long tv = gcd(v, pair.first);  
                if (tv != v) {  
                    g[i].push_back({tv, pair.second});  
                }  
                v = tv;  
                if (v == 1) break;  
            }  
        }  
    }  
    vector<int> res;  
    for (int i = 0; i < q; i++) {  
        int l, r;  
        cin >> l >> r;  
        l--;  // adjust for zero-based indexing  
        r--;  // adjust for zero-based indexing  
        auto& rightList = g[r];  
        int left = 0, right = rightList.size() - 1;  
        while (left <= right) {  
            int mid = left + (right - left) / 2;  
            if (rightList[mid].second >= l) {  
                left = mid + 1;  
            } else {  
                right = mid - 1;  
            }  
        }  
        res.push_back(left);  
    }  
    for (auto& val : res) cout << val << "\n";  
    return 0;  
}