【质因数指数，双指针】倍乘

https://www.luogu.com.cn/problem/P15019

题意概括

给定长度为 $n$ 的数组 $a$。

一次“数组倍乘”会对每个元素 $a\_i$ 独立选择一个除数 $d\_i$，并将其变为 $a\_i d\_i$。

对于一个区间 $\[l,r]$，如果能够通过至多 $k$ 次数组倍乘，使区间内所有元素相等，那么 $(l,r)$ 是优美数对。

需要统计优美数对的数量。

题目保证所有数的质因数均小于 $30$，因此只可能出现以下 $10$ 个质数：

$2,3,5,7,11,13,17,19,23,29.$

样例分析

考虑第一个样例中的区间 $\[1,3]$：

$ 6=2^1\cdot 3^1, \qquad 18=2^1\cdot 3^2, \qquad 12=2^2\cdot 3^1. $

对于质因数 $2$，三个数的指数分别为

$1,1,2.$

当 $k=1$ 时，一个指数最多扩大为原来的 $2$ 倍，因此最大指数 $2$ 不超过最小指数 $1$ 的 $2$ 倍。

对于质因数 $3$，指数分别为

$1,2,1,$

同样满足条件。

于是可以把三个数都变成

$36=2^2\cdot 3^2.$

再考虑区间 $\[1,4]$。第四个数为

$24=2^3\cdot 3.$

此时质因数 $2$ 的最小指数为 $1$，最大指数为 $3$。一次操作最多将指数 $1$ 变为 $2$，无法达到 $3$，所以该区间不合法。

这个例子说明，问题的关键不在数值本身，而在每个质因数的指数。

算法思路

整体思路

将每个数分解成 $10$ 个质因数的指数向量。

对于每个质因数分别研究一次操作如何改变它的指数，可以证明：指数 $c$ 经过至多 $k$ 次操作后，可以变成区间

$\[c,2^k c]$

中的任意整数。

因此，一个区间合法，当且仅当对于每个质因数，该区间中的最大指数都不超过最小指数的 $2^k$ 倍。

这个条件在删除区间端点后仍然成立，因此具有子区间单调性。可以使用双指针维护当前合法窗口，并统计所有合法子区间。

推导过程

1. 一次操作怎样改变质因数指数

设当前数字为

$x=\prod\_p p^{c\_p}.$

它的任意除数可以写成

$d=\prod\_p p^{b\_p},$

其中对每个质数 $p$，都有

$0\le b\_p\le c\_p.$

执行一次操作后，

$x\leftarrow xd,$

所以质因数 $p$ 的指数从 $c\_p$ 变为

$c\_p+b\_p.$

因为 $0\le b\_p\le c\_p$，新指数可以是

$c\_p,c\_p+1,\ldots,2c\_p$

中的任意一个值。

不同质因数对应的 $b\_p$ 可以独立选择，所以可以分别研究每个质因数。

2. 经过 $k$ 次操作后的可达范围

设某个质因数的初始指数为 $c$。

经过一次操作，可以到达 $\[c,2c]$ 中的任意整数。经过两次操作，可以到达 $\[c,4c]$ 中的任意整数。

一般地，经过至多 $k$ 次操作后，能够到达的指数恰好是

$c,c+1,\ldots,2^k c.$

下面说明为什么这个区间内不存在空缺。

假设经过 $t$ 次操作，可以到达 $\[c,2^t c]$ 中的任意整数。现在希望经过 $t+1$ 次到达指数 $y$，其中

$c\le y\le 2^{t+1}c.$

只需要选择一个中间指数 $z$，满足

$c\le z\le 2^t c, \qquad z\le y\le 2z.$

这样的 $z$ 总能取到，例如可以从 $\max(c,\lceil y/2\rceil)$ 附近选择。

根据归纳假设，前 $t$ 次操作可以到达 $z$，最后一次操作再从 $z$ 到达 $y$。

当 $c=0$ 时，可达范围只有 $0$。这说明一个数原本不含某个质因数，就永远无法通过操作产生这个质因数。

3. 一个区间什么时候合法

设 $c\_{i,p}$ 表示 $a\_i$ 中质因数 $p$ 的指数。

如果区间 $\[l,r]$ 最终全部变成同一个数，那么对于每个质因数 $p$，最终指数 $t\_p$ 必须同时满足

$c\_{i,p}\le t\_p\le 2^k c\_{i,p}$

对所有 $l\le i\le r$ 成立。

将所有下界合并，得到

$t\_p\ge \max\_{l\le i\le r}c\_{i,p}.$

将所有上界合并，得到

$t\_p\le 2^k\min\_{l\le i\le r}c\_{i,p}.$

因此存在合法的 $t\_p$，当且仅当

$ \max\_{l\le i\le r}c\_{i,p} \le 2^k\min\_{l\le i\le r}c\_{i,p}. $

这个条件需要对全部 $10$ 个质因数同时成立。

所以区间 $\[l,r]$ 合法的充要条件为

$ \forall p,\qquad \max\_{l\le i\le r}c\_{i,p} \le 2^k\min\_{l\le i\le r}c\_{i,p}. $

这也包含了质因数集合不同的情况。

例如某个数不含质因数 $p$，另一个数含有 $p$，那么最小指数为 $0$，最大指数大于 $0$，不等式一定不成立。

4. 为什么可以使用双指针

如果区间 $\[l,r]$ 合法，删除其中任意一些元素后：

• 每个质因数的最大指数只可能减小。
• 每个质因数的最小指数只可能增大。

所以合法区间的任意子区间仍然合法。

固定右端点 $r$。假设最小的合法左端点是 $l$，那么

$\[l,r],\[l+1,r],\ldots,\[r,r]$

全部合法，共有

$r-l+1$

个。

而所有左端点小于 $l$ 的区间都不合法。

因此可以从左到右枚举右端点 $r$，不断将 $a\_r$ 加入窗口。如果当前窗口不合法，就持续右移左端点 $l$，直到窗口重新合法。

每个元素最多进入窗口一次并离开窗口一次。

5. 怎样维护最大指数和最小指数

每个 $a\_i\le 10^6$，因此任意质因数的指数不超过 $19$，因为

$2^{19}\le 10^6<2^{20}.$

对每个质因数维护：

$\operatorname{cnt}\_{p,v}$

表示当前窗口中，质因数 $p$ 的指数等于 $v$ 的元素数量。

同时维护：

• $\operatorname{mn}\_p$：当前最小指数。
• $\operatorname{mx}\_p$：当前最大指数。

加入元素时直接更新计数和极值。

删除元素后，如果被删除的指数是当前极值，并且它的出现次数变为 $0$，就在 $0$ 到 $20$ 的小范围内寻找新的极值。

算法流程

1. 保存所有小于 $30$ 的质数。

2. 将每个 $a\_i$ 分解为这 $10$ 个质数的指数，记录为 $c\_{i,p}$。

3. 初始化左端点 $l=1$，答案为 $0$。

4. 从左到右枚举右端点 $r$。

5. 将 $a\_r$ 的全部质因数指数加入窗口。

6. 检查是否对每个质因数都有

   $\operatorname{mx}\_p\le 2^k\operatorname{mn}\_p.$

7. 如果条件不成立，就删除 $a\_l$，然后令 $l\leftarrow l+1$，直到窗口合法。

8. 当前所有合法左端点为 $l,l+1,\ldots,r$，将

   $r-l+1$

   加入答案。

9. 输出答案。

正确性说明

引理一

若某个质因数的初始指数为 $c$，则经过至多 $k$ 次操作后，可以到达且只能到达区间 $\[c,2^k c]$ 中的整数指数。

证明：

每次操作只能给当前指数增加一个不超过当前指数的非负整数，所以指数不会减小，并且一次操作后至多翻倍。因此经过 $k$ 次操作后，指数一定处于 $\[c,2^k c]$。

另一方面，通过归纳可以证明该区间中的每个整数都可达。若目标指数为 $y$，可以选择一个已经能够到达的中间指数 $z$，使 $z\le y\le 2z$，最后一次操作增加 $y-z$ 即可。

因此结论成立。

引理二

区间 $\[l,r]$ 合法，当且仅当对于每个质因数 $p$，都有

$ \max\_{l\le i\le r}c\_{i,p} \le 2^k\min\_{l\le i\le r}c\_{i,p}. $

证明：

根据引理一，元素 $a\_i$ 的质因数 $p$ 的最终指数必须位于

$\[c\_{i,p},2^k c\_{i,p}]$

中。

所有元素能够取得同一个最终指数，当且仅当这些区间存在公共交集。

公共交集非空的条件正是最大下界不超过最小上界，即

$ \max\_{l\le i\le r}c\_{i,p} \le 2^k\min\_{l\le i\le r}c\_{i,p}. $

不同质因数可以独立选择最终指数，因此该条件对所有质因数成立时，整个区间可以变成相同的数。

引理三

对于固定右端点 $r$，双指针停止后，以 $r$ 为右端点的合法区间恰好有 $r-l+1$ 个。

证明：

循环停止时，区间 $\[l,r]$ 合法。

合法性在删除元素后不会被破坏，所以

$\[l,r],\[l+1,r],\ldots,\[r,r]$

全部合法。

对于任意 $x\<l$，左端点从 $x$ 被删除时，区间 $\[x,r]$ 仍然不合法，因此这些区间不能计入答案。

所以合法区间恰好有 $r-l+1$ 个。

定理

算法输出的答案等于所有优美数对的数量。

证明：

根据引理二，程序维护的判定条件与题目中的区间合法条件完全等价。

根据引理三，每次处理右端点 $r$ 时，程序准确统计所有以 $r$ 为右端点的合法区间，没有遗漏，也没有重复。

所有区间都有唯一的右端点，因此最终答案恰好是全部优美数对数量。

实现细节与易错点

1. 输入中的 $g$ 只表示测试点区块编号，不参与计算。

2. 当 $k$ 很大时不能直接计算 $2^k$，否则会发生位移溢出。由于质因数指数最大只有 $19$，将 $k$ 截断到 $20$ 不会影响判定。

3. 指数为 $0$ 必须正常加入计数数组。它表示该数不含对应质因数。

4. 当最小指数为 $0$ 时，判定式要求最大指数也必须为 $0$。这正好保证区间内所有数的质因数集合一致。

5. 区间数量最多为

$\frac{n(n+1)}2,$

需要使用 long long 保存答案。

参考实现

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

const int N = 200005;
int a[N][10], ct[10][21], mn[10], mx[10];
int p[10] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
ll c;

void ad(int x) {
    for(int i = 0; i < 10; i++) {
        int v = a[x][i];
        ct[i][v]++;
        mn[i] = min(mn[i], v);
        mx[i] = max(mx[i], v);
    }
}

void dl(int x) {
    for(int i = 0; i < 10; i++) {
        int v = a[x][i];
        ct[i][v]--;

        if(v == mn[i] && ct[i][v] == 0) {
            while(mn[i] <= 20 && ct[i][mn[i]] == 0) mn[i]++;
        }

        if(v == mx[i] && ct[i][v] == 0) {
            while(mx[i] >= 0 && ct[i][mx[i]] == 0) mx[i]--;
        }
    }
}

bool ck() {
    for(int i = 0; i < 10; i++) {
        if(mx[i] > c * mn[i]) return 0;
    }
    return 1;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n, k, g;
    cin >> n >> k >> g;

    for(int i = 1; i <= n; i++) {
        int x;
        cin >> x;

        for(int j = 0; j < 10; j++) {
            while(x % p[j] == 0) {
                a[i][j]++;
                x /= p[j];
            }
        }
    }

    for(int i = 0; i < 10; i++) {
        mn[i] = 20;
        mx[i] = -1;
    }

    c = 1LL << min(k, 20);

    ll ans = 0;
    int l = 1;

    for(int r = 1; r <= n; r++) {
        ad(r);

        while(!ck()) {
            dl(l);
            l++;
        }

        ans += r - l + 1;
    }

    cout << ans << '\n';
    return 0;
}

复杂度分析

设可能出现的质数数量为 $P=10$，质因数指数的值域大小为 $E=20$。

分解全部元素和维护双指针窗口的时间复杂度为

$O(nPE).$

因为 $P$ 和 $E$ 都是固定常数，所以总时间复杂度为

$O(n).$

保存每个元素的质因数指数需要 $O(nP)$ 空间，因此总空间复杂度为

$O(n).$