1410：最大质因子序列

最大质因子序列是指将一个正整数反复分解为最大质因子的连续操作，直到不能再分解为止。具体步骤如下：

1. 给定一个正整数n。
2. 找到n的最大质因子p。
3. 将n除以p，得到商q。
4. 如果q是一个质数，则停止分解，最大质因子序列结束。
5. 如果q不是质数，则继续找到q的最大质因子，重复步骤2-4。

举个例子，假设n=1410：

1. 最大质因子是3，将1410除以3得到470。
2. 最大质因子是2，将470除以2得到235。
3. 最大质因子是5，将235除以5得到47。
4. 47是一个质数，停止分解，最大质因子序列结束。

因此，1410的最大质因子序列为3, 2, 5, 47。

相关问题

吃++中一堆数的子序列

题目描述：

给定一个长度为n的正整数序列 a1,a2,…,an，你需要选出一个非空子序列，使得这个子序列中的数的乘积模 109+7 的值最大。

数据范围：1≤n≤105，1≤ai≤103。

样例：

输入：

3

1 2 3

输出：

6

输入：

4

1 2 3 4

输出：

24

算法1：

(暴力枚举) $O(n^2)$

枚举所有子序列，计算乘积并取模，记录最大值。

时间复杂度

枚举子序列需要 $O(n^2)$，计算乘积需要 $O(n)$，所以总时间复杂度为 $O(n^3)$。

C++ 代码

算法2：

(贪心) $O(n)$

由于模数为质数，我们可以使用费马小定理求乘法逆元。

对于每个数，我们可以先把它分解质因数，然后对于每个质因子，我们可以计算出它在所有子序列中出现的次数，这个次数是 $2^n-1$，其中 $n$ 是这个质因子出现的次数。我们可以使用快速幂计算 $2^n-1$，然后乘上这个质因子，最后再将所有质因子的积取模，就得到了最大乘积。

时间复杂度

每个数需要分解质因数，时间复杂度为 $O(\sqrt{n}\log n)$，计算每个质因子的次数需要用到快速幂，时间复杂度为 $O(\log p)$，总时间复杂度为 $O(n\sqrt{n}\log n)$。

C++ 代码

给出一个长度为n(1≤n≤2.105）的序列a(1≤ai≤109)，并且保证序列a所有元素乘积≤1018，求这个序列中满足如下条件的连续子段[at...ar]的数量: •令x＝a{：a1+1·a1+2...ar，那么x的末尾恰好有k(0≤k≤109)个零。给出c++代码

好的，以下是实现了上述算法的C++代码：

#include <iostream>
#include <map>
#include <vector>

using namespace std;

const int MAXN = 2e5 + 5;

int n, k;
long long a[MAXN], p[MAXN];
map<int, int> cnt;

int main() {
    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        p[i] = p[i - 1] + a[i];
    }

    long long ans = 0;
    cnt[0] = 1;
    for(int r = 1; r <= n; r++) {
        int t = p[r] % 10;
        if(t == 0) ans++; // 特判末尾为0的情况
        while(t % 2 == 0) t /= 2;
        while(t % 5 == 0) {
            t /= 5;
            cnt[0]++;
        }
        for(int i = 1; i <= k; i++) {
            if(i <= cnt.size() - 1 && cnt[i] > 0) {
                ans += cnt[i];
            }
            if(cnt.find(i) == cnt.end()) {
                cnt[i] = 0;
            }
        }
        if(cnt.find(k) != cnt.end() && cnt[k] > 0) {
            int l = 1, r = cnt[k - 1];
            while(l <= r) {
                int mid = (l + r) / 2;
                if(cnt[k] - cnt[k - 1] + cnt[k - mid - 1] >= 1) {
                    r = mid - 1;
                } else {
                    l = mid + 1;
                }
            }
            ans += l;
        }
        cnt[t]++;
    }

    cout << ans << endl;
    return 0;
}

其中，cnt数组维护了左端点l到当前右端点r中质因子分解后包含i个质因子5的数的个数。在这个代码中，我们使用了一个map来实现cnt数组，这样可以避免数组空间过大的问题。

在代码中，我们对每个右端点r维护cnt数组，然后利用二分找到满足条件的最小左端点l。具体来说，我们先用二分找到满足条件的最小k，然后从k向0遍历，每次将cnt[k]加到cnt[k-1]中，表示当前k个5的数都可以向左扩展一位，然后再用二分找到满足cnt[k-1]≥1的最小的l即可。

时间复杂度为O(nlognlogm)，其中m是序列中最大的数的质因子个数。