一类子区间gcd，按位与，按位或的问题

有 $T$ 组询问，每次给出 $n$ 个数 $a_i$。[P7009 CERC2013] Magical GCD - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

你需要找到这个数组的一个子序列（要求编号连续），使得该序列中所有数的最大公约数和序列长度的乘积最大，并输出这个最大值。

Sol:重要性质如果右端点不同，那么gcd意义下本质不同的左端点只有log个https://www.luogu.com.cn/problem/P5502

include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N=1e5+10;
#define LL long long
queue<int>q,r;
int n;LL a[N],res;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
int main()
{
	int T;scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);res=0;
		for(int i=1;i<=n;i++)
		{
			scanf("%lld",&a[i]);LL last=0;res=max(res,a[i]);
			while(!q.empty())
			{
				int x=q.front();q.pop();a[x]=gcd(a[x],a[i]);//x就是最小的满足区间[x,i]的gcd为a[x]的左端点 
				res=max(res,a[x]*(i-x+1));
				if(a[x]==a[last]) continue;//一些左端点就可以合并掉 
				r.push(x);last=x;
			}
			while(!r.empty())
			{
				q.push(r.front());
				r.pop();
			}
			if(a[last]!=a[i]) q.push(i);//i也可以作为一个新的左端点 
	 	}
		printf("%lld\n",res);
		while(!q.empty()) q.pop();
	}
	return 0;
}

Sol2:解法2：固定左端点，用于倍增优化右端点的确定(其实也可以二分）。但是在倍增的过程中，需要多次查询区间最大公约数；我们可以用ST表的思路对序列预处理，做到 O*(1) 复杂度查询。

  • 稍加观察，可以发现当左端点确定时，右端点右移一个单位，原子段的最大公约数要么维持不变；要么变为原最大公约数的一个约数。换言之，当左端点确定时，不同的右端点最多对应 log⁡2𝑛log2n 个不同的最大公约数值。算法复杂度得以控制在 $𝑂(𝑛(log⁡𝑛)^2) $。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

int T, N;
ll ans;
ll a[100005];
ll st[100005][18];
int lg[100005];

inline ll query(int l, int r) {
    int k = lg[r - l + 1];
    return gcd(st[l][k], st[r - (1 << k) + 1][k]);
}

int main() {
    lg[1] = 0;
    for (int  i = 2; i <= 100000; ++i)
        lg[i] = lg[i >> 1] + 1;
    scanf("%d", &N);
    for ( int i = 1; i <= N; ++i)
        scanf("%lld", &st[i][0]);
    for (  int j = 1; j <= lg[N]; ++j)
        for (  int i = 1; i + (1 << j) - 1 <= N; ++i)
            st[i][j] = gcd(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
    for (  int l = 1; l <= N; ++l) {
        int r = l;
        while (r <= N) {
            ll cur = query(l, r);
            for (  int i = lg[N]; i >= 0; --i) {
                if (r + (1 << i) <= N && query(l, r + (1 << i)) == cur)
                    r += (1 << i);
            }
            ans = max(ans, cur * (r - l + 1));
            r += 1;
        }
    }
    printf("%lld", ans);
    return 0;
}

二分写法

#include <bits/stdc++.h>
using namespace std;
int n, T;
long long gcd[100001][21], maxx;
long long gcdqj(int l, int r)
{
    int p = log2(r - l + 1);
    return __gcd(gcd[l][p], gcd[r - (1 << p) + 1][p]);
}
int search(int i, int l, int r, long long value)
{
    while (r - l > 1)
    {
        int mid = (l + r) / 2;
        if (gcdqj(i, mid) == value)
            l = mid;
        else
            r = mid - 1;
    }
    if (gcdqj(i, r) == value)
        return r;
    return l;
}
int main()
{
    cin >> T;
    while (T--)
    {
        cin >> n;
        for (int i = 1; i <= n; i++)
            cin >> gcd[i][0];
        for (int i = 1; i <= 20; i++)
            for (int j = 1; j + (1 << i) - 1 <= n; j++)
                gcd[j][i] = __gcd(gcd[j][i - 1], gcd[j + (1 << i - 1)][i - 1]);
        maxx = 0;
        for (int i = 1; i <= n; i++)
        {
            for (int l = i, r = 0; l <= n; l = r + 1)
            {
                r = search(i, l, n, gcdqj(i, l));
                maxx = max(maxx, (r - i + 1) * gcdqj(i, l));
            }
        }
        cout << maxx << endl;
    }
}
https://ac.nowcoder.com/acm/contest/76681/K

求所有数组子区间的区间gcd之和

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

inline ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

ll T, N;

ll a[200005];
ll st[200005][20];
int lg[200005];
//const int mod = 998244353;
inline ll query(int l, int r) {
    int k = lg[r - l + 1];
    return gcd(st[l][k], st[r - (1 << k) + 1][k]);
}
//int ans[200005];
//int cnt[200005];

Z ans=0;
int main() {
    lg[1] = 0;
    for ( int i = 2; i <= 200000; ++i)
        lg[i] = lg[i >> 1] + 1;
    scanf("%lld", &N);
    for ( int i = 1; i <= N; ++i)
        scanf("%lld", &st[i][0]);
    for (int j = 1; j <= lg[N]; ++j)
        for (int i = 1; i + (1 << j) - 1 <= N; ++i)
     st[i][j] = gcd(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
    for ( int l = 1; l <= N; ++l) {
        int r = l;
        int last=l;
        while (r <= N) {
            ll cur = query(l, r);
            for ( int i = lg[N]; i >= 0; --i) {
                if (r + (1 << i) <= N && query(l, r + (1 << i)) == cur)
                    r += (1 << i);
            }
            Z len=r-last+1;
            ans+=len*(last-l+1+r-l+1)*cur/2;
              last=r+1;
        
            r += 1;
        }
       
    }
  
    Z tmp=(N*(N+1)/2);
    Z res=tmp.inv()*ans;
 cout<<res<<endl;
    return 0;
}

题意：另一个重要性质

给出一个长度为n的序列和q次询问，每次询问把序列中的每个元素加上x，输出整个序列的gcd。

思路：
我们都知道gcd(a,b)=gcd(a,b-a)
对于多个数组而言，gcd(a,b,c,d)=gcd(a,b-a,c-b,d-c)
所以gcd(a+x,b+x,c+x,d+x)=gcd(a+x,b-a,c-b,d-c)
这就是gcd的更相减损性。
————————————————

链接：https://ac.nowcoder.com/acm/contest/96/I

给一个数列共n(n<=100,000)个数，a1,a2,…,an.(0<=ai<=1000,000,000).有q(q<=100,000)个询问。每个询问为l,r(1<=l<=r<=n).求gcd(al,al+1,…,ar). 再求区间[l,r]的子区间中(l<=l’<=r’<=r)满足gcd(al,al+1,…,ar) = gcd(al’,al’+1,…ar’)的子区间个数.

image-20240512014736082

#include <bits/stdc++.h>
#define rep(i,j,k) for (int i = j; i <= k; i++)
#define per(i,j,k) for (int i = j; i >= k; i--)
#define loop(i,j,k) for (int i = j;i != -1; i = k[i])
#define lson x << 1, l, mid
#define rson x << 1 | 1, mid + 1, r
#define ff first
#define ss second
#define mp(i,j) make_pair(i,j)
#define pb push_back
#define pii pair<int,LL>
#define in(x) scanf("%d", &x);
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const double eps = 1e-4;
const int INF = 0x7FFFFFFF;
const int N = 4e5 + 10;
int T, n, m, l, r;
int g[N],d[N];
  
long long s[N], k[N];
  
int gcd(int x, int y) {
    return x%y ? gcd(y, x%y) : y;
}
  
void build(int x,int l,int r) {
    if (l == r) {
        scanf("%d",&g[x]);
        d[r] = g[x];
    }
    else {
        int mid = l + r >> 1;
        build(lson);
        build(rson);
        g[x] = gcd(g[x<<1], g[x<<1|1]);
    }
}
  
int query(int x,int l,int r,int ll,int rr) {
    if (ll<=l && r<=rr) return g[x];
    int mid = l + r>>1;
    if (rr <= mid) return query(lson,ll,rr);
    else if (ll > mid) return query(rson,ll,rr);
    else return gcd(query(lson,ll,rr),query(rson,ll,rr));
}
  
void pushUp(int rt) {
    s[rt] = s[2 * rt] + s[2 * rt + 1];
}
  
void pushDown(int rt, int l, int r) {
    if(k[rt] == 0) return;
    int mid = (l + r) / 2;
    s[2 * rt] += (k[rt] * (mid - l + 1));
    s[2 * rt + 1] += (k[rt] * (r - mid));
    k[2 * rt] += k[rt];
    k[2 * rt + 1] += k[rt];
    k[rt] = 0;
}
  
void update(int L, int R, long long val, int l, int r, int rt) {
    if(L <= l && r <= R) {
        s[rt] += (val * (r - l + 1));
        k[rt] += val;
        return;
    }
    int mid = (l + r) / 2;
    pushDown(rt, l, r);
    if(L <= mid) update(L, R, val, l, mid, 2 * rt);
    if(R > mid) update(L, R, val, mid + 1, r, 2 * rt + 1);
    pushUp(rt);
}
  
long long get(int L, int R, int l, int r, int rt) {
    if(L <= l && r <= R) return s[rt];
    pushDown(rt, l, r);
    int mid = (l + r) / 2;
    long long left = 0, right = 0;
    if(L <= mid) left = get(L, R, l, mid, 2 * rt);
    if(R > mid) right = get(L, R, mid + 1, r, 2 * rt + 1);
    pushUp(rt);
    return left + right;
}
  
struct point{
    int l,r,g, id;
}c[N];
  
struct point2 {
    int l1, l2, r, g;
}h[N];
int szh;
  
long long ans[N];
  
bool cmpc(const point& a, const point& b) {
    if(a.g != b.g) return a.g < b.g;
    return a.r < b.r;
}
  
bool cmph(const point2& a, const point2& b) {
    if(a.g != b.g) return a.g < b.g;
    return a.r < b.r;
}
  
bool cmpid(const point& a, const point& b ) {
    return a.id < b.id;
}
  
int main() {
#ifdef ZHOUZHENTAO
    freopen("test.in", "r", stdin);
#endif
  
    scanf("%d", &T);
    int cas = 0;
    while (T--) {
        scanf("%d", &n);
        build(1, 1, n);
        scanf("%d", &m);
        printf("Case #%d:\n", ++cas);
        for (int i = 0;i< m ;i++) {
            scanf("%d%d", &c[i].l, &c[i].r);
            c[i].g = query(1, 1, n, c[i].l, c[i].r);
            c[i].id = i;
        }
  
        szh = 0;
        stack<pii> a, b;
        rep(i, 1, n) {
            a.push(mp(d[i], 1));
            while (!a.empty()) b.push(mp(gcd(a.top().ff, d[i]), a.top().ss)), a.pop();
            while (!b.empty()) {
                pii q = b.top();    b.pop();
                if (!a.empty() && a.top().ff == q.ff) q.ss += a.top().ss, a.pop();
                a.push(q);
            }
  
            int L = i;
            while (!a.empty()) {
                pii q = a.top(); a.pop();
                int LL = L - q.second + 1;
                h[szh].l1 = LL;
                h[szh].l2 = L;
                h[szh].r = i;
                h[szh].g = q.first;
                szh ++;
                L = LL - 1;
                b.push(q);
            }
            while (!b.empty()) {
                a.push(b.top()); b.pop();
            }
        }
  
        sort(c, c + m, cmpc);
        sort(h, h + szh, cmph);
        /*
                for(int i = 0; i < szh; i ++) {
                cout << h[i].l1 << " " << h[i].l2 << " " << h[i].r << " " << h[i].g << endl;
                }
  
                for(int i = 0; i < m; i ++) {
                cout << c[i].l << " " << c[i].r << " " << c[i].g << endl;
                }
         */
        for(int i = 0; i < m; i ++) {
            ans[i] = 0;
        }
        for(int i = 0, j = 0; i < szh; i = j + 1, j = i) {
            while(j < szh - 1 && h[j].g == h[j + 1].g) j ++;
            // [i, j]
  
            int L = 0, R = m - 1, pos1 = -1, pos2 = -1;
            while(L <= R) {
                int mid = (L + R) / 2;
                if(c[mid].g < h[i].g) L = mid + 1;
                else if(c[mid].g > h[i].g) R = mid - 1;
                else pos1 = mid, R = mid - 1;
            }
  
            if(pos1 == -1) continue;
  
            L = 0, R = m - 1;
            while(L <= R) {
                int mid = (L + R) / 2;
                if(c[mid].g < h[i].g) L = mid + 1;
                else if(c[mid].g > h[i].g) R = mid - 1;
                else pos2 = mid, L = mid + 1;
            }
  
            //[pos1, pos2]
            /*
                 printf("[%d, %d]  [%d, %d]\n", i, j, pos1, pos2);
             */
            int y = i;
            for(int k = pos1; k <= pos2; k ++) {
                while(y <= j && h[y].r <= c[k].r) {
                    update(h[y].l1, h[y].l2, 1LL, 1, n, 1);
                    y ++;
                }
                ans[c[k].id] = get(c[k].l, c[k].r, 1, n, 1);
            }
  
            for(int k = i; k < y; k ++) {
                update(h[k].l1, h[k].l2, -1LL, 1, n, 1);
            }
  
        }
  
        sort(c, c + m, cmpid);
        for(int i = 0; i < m; i ++) {
            printf("%d ", c[i].g);
            printf("%lld\n", ans[i]);
        }
  
    }
    return 0;
}