C++程序用于范围LCM查询

什么是LCM

LCM全称为Least Common Multiple，是最小公倍数的意思。也就是说，假设a和b为两个正整数，我们要找到一个正整数c，使得a和b都能被c整除，且c是所有满足该条件的正整数中最小的一个。

例如，a=12，b=18，则c=36是a和b的最小公倍数，因为12和18都能够被36整除，且其他能够被12和18整除的正整数（如24、48等）都无法小于36。

范围LCM查询

先来看一个简单的问题：给定两个整数a和b，求它们的最小公倍数LCM。

这个问题比较简单，我们可以直接套用LCM的定义，先求出a和b的一个公共因子d，然后用a×b÷d就可以得到最小公倍数LCM。

接下来我们来考虑一个稍微复杂一点的问题：给定一个长度为n的整数序列，求出区间[l,r]内所有数的最小公倍数。

这个问题该怎么解决呢？我们可以把LCM的定义推广到一组数上：

设a1,a2,…,an是n个正整数，它们的最小公倍数为LCM(a1,a2,…,an)。首先，我们可以将a1,a2,…,an分解为它们的质因数：

a1＝p1^k1 × p2^k2 × … × pm^km
a2＝p1^l1 × p2^l2 × … × pm^lm
…
an＝p1^x1 × p2^x2 × … × pm^xm

其中，p1,p2,…,pm均为质数，k1,k2,…,km,l1,l2,…,lm,…,x1,x2,…,xm均为非负整数。LCM(a1,a2,…,an)可以表示为

LCM(a1,a2,…,an)＝p1^max{k1,l1,…,x1} × p2^max{k2,l2,…,x2} × … × pm^max{km,lm,…,xm}

这个式子看着比较复杂，但实际上不难理解。这里的max{k1,l1,…,x1}表示k1,l1,…,x1中的最大值，意思是p1要乘以的次数等于a1,a2,…,an中p1出现的最大次数。这样，我们只需统计[l,r]中每个数的质因数分解式，然后按照上面的公式求出lcm。

下面是使用C++实现此算法的示例代码：

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

typedef long long ll;

const int MAXN = 1e5;

int n, m, blocksize, l, r;
int a[MAXN + 5], cnt[MAXN + 5], prime[MAXN + 5], vis[MAXN + 5], mu[MAXN + 5], mindiv[MAXN + 5];
ll ans;

inline ll read() { //快读
    ll x = 0; char c = getchar();
    while(!isdigit(c)) c = getchar();
    while(isdigit(c)) x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    return x;
}

inline void sieve(int n) { //线性筛
    mu[1] = 1;
    for(int i = 2; i <= n; i++) {
        if(!vis[i]) { prime[++m] = i; mindiv[i] = i; mu[i] = -1; }
        for(int j = 1; j <= m && i * prime[j] <= n; j++) {
            vis[i * prime[j]] = 1;
            mindiv[i * prime[j]] = prime[j];
            if(i %prime[j] == 0) { mu[i * prime[j]] = 0; break; }
            mu[i * prime[j]] = -mu[i];
            if(mindiv[i] == prime[j]) break;
        }
    }
}

inline void add(int x) { //区间加数
    ans -= 1ll * cnt[x] * cnt[x] * mu[x];
    cnt[x]++;
    ans += 1ll * cnt[x] * cnt[x] * mu[x];
}

inline void del(int x) { //区间减数
    ans -= 1ll * cnt[x] * cnt[x] * mu[x];
    cnt[x]--;
    ans += 1ll * cnt[x] * cnt[x] * mu[x];
}

int main() {
    n = read();
    sieve(n);
    blocksize = sqrt(n);
    for(int i = 1; i <= n; i++) a[i] = read();
    for(int i = 1; i <= n; i += blocksize) {
        int l = i, r = min(n, i + blocksize - 1);
        memset(cnt, 0, sizeof(cnt));
        ans = 0;
        for(int j = l; j <= r; j++) add(a[j]);
        printf("区间[%d, %d]的Lcm为：%lld\n", l, r, ans);
        while(l <= r) {
            del(a[l]);
            l++;
            if(l > r) break;
            printf("区间[%d, %d]的Lcm为：%lld\n", l, r, ans);
        }
    }
    return 0;
}

这段代码中，我们采用了分块的思想，将整个序列分成若干块，每块长度为sqrt(n)，这样每次查询区间[l,r]内所有数的最小公倍数，只需要枚举区间的左端点l，然后通过区间加减数（add和del）来维护答案。这样，总时间复杂度可以降为O(nsqrt(n))，即使在n较大时，也能够快速地求解。