题意 : 给出一个有 N 个数字的整数数列、给出 Q 个问询、每次问询给出一个区间、用 ( L、R ) 表示、要你统计这个整数数列所有的子区间中有多少个和 GCD( L ~ R ) 相等、输出 GCD( L ~ R ) 以及子区间个数
分析 :
首先对于给出一个区间要你给出 GCD
这个操作可以使用线段树来做、线段树是可以维护 GCD 的
但是由于这题的静态区间 (即数列里面的数不会被改变)
那么也有另外一种方法来回答区间 GCD 的问询
预处理的复杂度是 O(nlogn) 、问询是 O(1)
即 ST表、类似处理 RMQ 问题那样子把代码改成求 GCD 就行了
其次它还要你给出和问询区间 GCD 一样的子区间的个数
考虑预处理出所有出现的 GCD 到底在多少个不同的子区间出现过
用 map 存一下也能够做到复杂度在 O(nlogn) 内
这个的处理需要用到二分技巧、还有一点数学知识
首先如果固定区间左端点、那么右端点越大、则 GCD 必定单调不增
所以可以考虑枚举所有的位置作为左端点
然后通过二分的方式找出所有以左端点为开头的 GCD 一样的区间
例如 2 4 6 5 1
枚举 2 作为左端点时候、那么第一次二分会二分到 6 的位置
即 2 4 6 的 GCD 都是 2、则 mp[2] += pos(6) - pos(2) + 1 = 3 - 1 + 1 = 3
然后将 GCD 改变一下变成 GCD = gcd( GCD, 5 )
此时 GCD 会变成 1 、那么第二次二分就会二分到 1 的位置
所以 mp[1] = pos(1) - pos(5) + 1 = 2
接下来就以 4 为左端点、以此类推........
但是你可能会有忧虑、即使是这样子的二分、会不会因为二分次数太多超时
那么你考虑一下、对于端点 L 、其数值是 arr[L]
那么以它为左端点的区间的 GCD 必定是 arr[L] 质因子的某些乘积组合
每加入一个能够改变 GCD 的数、则 GCD 必定减少至少两倍
质因子的数量的 log 的、那么每次二分必定不超过 log(1e9) 次
#include<bits/stdc++.h> #define LL long long #define ULL unsigned long long #define scl(i) scanf("%lld", &i) #define scll(i, j) scanf("%lld %lld", &i, &j) #define sclll(i, j, k) scanf("%lld %lld %lld", &i, &j, &k) #define scllll(i, j, k, l) scanf("%lld %lld %lld %lld", &i, &j, &k, &l) #define scs(i) scanf("%s", i) #define sci(i) scanf("%d", &i) #define scd(i) scanf("%lf", &i) #define scIl(i) scanf("%I64d", &i) #define scii(i, j) scanf("%d %d", &i, &j) #define scdd(i, j) scanf("%lf %lf", &i, &j) #define scIll(i, j) scanf("%I64d %I64d", &i, &j) #define sciii(i, j, k) scanf("%d %d %d", &i, &j, &k) #define scddd(i, j, k) scanf("%lf %lf %lf", &i, &j, &k) #define scIlll(i, j, k) scanf("%I64d %I64d %I64d", &i, &j, &k) #define sciiii(i, j, k, l) scanf("%d %d %d %d", &i, &j, &k, &l) #define scdddd(i, j, k, l) scanf("%lf %lf %lf %lf", &i, &j, &k, &l) #define scIllll(i, j, k, l) scanf("%I64d %I64d %I64d %I64d", &i, &j, &k, &l) #define lson l, m, rt<<1 #define rson m+1, r, rt<<1|1 #define lowbit(i) (i & (-i)) #define mem(i, j) memset(i, j, sizeof(i)) #define fir first #define sec second #define VI vector<int> #define ins(i) insert(i) #define pb(i) push_back(i) #define pii pair<int, int> #define VL vector<long long> #define mk(i, j) make_pair(i, j) #define all(i) i.begin(), i.end() #define pll pair<long long, long long> #define _TIME 0 #define _INPUT 0 #define _OUTPUT 0 clock_t START, END; void __stTIME(); void __enTIME(); void __IOPUT(); using namespace std; const int maxn = (int)1e5 + 10; int N, Q; int arr[maxn]; int dp[maxn][18]; int idx[maxn]; map<int, LL> mp; inline void init_idx() { idx[0] = -1; for(int len=1; len<=N; len++) idx[len] = ((len & (len-1)) == 0) ? idx[len-1] + 1 : idx[len-1]; } inline void init_rmq() { for(int j=1; j<=17; j++){ for(int i=1; i+(1<<(j-1))<= N; i++){ dp[i][j] = __gcd(dp[i][j-1], dp[i+(1<<(j-1))][j-1]); } } } int RMQ(int L, int R) { int k = idx[R-L+1]; return __gcd(dp[L][k], dp[R-(1<<k)+1][k]); } inline void init_gcd_num() { for(int i=1; i<=N; i++){ int j = i; int GCD = arr[j]; while(j <= N){ int L, R, pos; L = pos = j; R = N; while(L <= R){ int mid = L + ((R-L)>>1); if(RMQ(i, mid) == GCD) L = mid+1, pos = mid; else R = mid-1; } mp[GCD] += 1LL * (pos - j + 1); j = pos + 1; GCD = RMQ(i, j); } } } int main(void){__stTIME();__IOPUT(); int nCase, Case = 0; sci(nCase); while(nCase--){ mp.clear(); sci(N); for(int i=1; i<=N; i++) sci(arr[i]), dp[i][0] = arr[i]; init_idx(); init_rmq(); init_gcd_num(); sci(Q); printf("Case #%d: ", ++Case); while(Q--){ int L, R; scii(L, R); int GCD = RMQ(L, R); printf("%d %lld ", GCD, mp[GCD]); } } __enTIME();return 0;} void __stTIME() { #if _TIME START = clock(); #endif } void __enTIME() { #if _TIME END = clock(); cerr<<"execute time = "<<(double)(END-START)/CLOCKS_PER_SEC<<endl; #endif } void __IOPUT() { #if _INPUT freopen("in.txt", "r", stdin); #endif #if _OUTPUT freopen("out.txt", "w", stdout); #endif }