题意 : 给出一个有 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;
;
int N, Q;
int arr[maxn];
];
int idx[maxn];
map<int, LL> mp;
inline void init_idx()
{
idx[] = -;
; len<=N; len++)
idx[len] = ((len & (len-)) == ) ? idx[len-] + : idx[len-];
}
inline void init_rmq()
{
; j<=; j++){
; i+(<<(j-))<= N; i++){
dp[i][j] = __gcd(dp[i][j-], dp[i+(<<(j-))][j-]);
}
}
}
int RMQ(int L, int R)
{
];
<<k)+][k]);
}
inline void init_gcd_num()
{
; 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){
);
, pos = mid;
;
}
mp[GCD] += 1LL * (pos - j + );
j = pos + ;
GCD = RMQ(i, j);
}
}
}
int main(void){__stTIME();__IOPUT();
;
sci(nCase);
while(nCase--){
mp.clear();
sci(N);
; i<=N; i++)
sci(arr[i]),
dp[i][] = arr[i];
init_idx();
init_rmq();
init_gcd_num();
sci(Q);
printf("Case #%d:\n", ++Case);
while(Q--){
int L, R;
scii(L, R);
int GCD = RMQ(L, R);
printf("%d %lld\n", GCD, mp[GCD]);
}
}
__enTIME();;}
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
}