文章目录

• 题目
• 一、主要思路
• 二、实现

---

题目

数组延伸

给定一个初始长度为 n 的数组 a 以及一个整数 x。

我们现在要对数组 a 进行延伸，具体方法如下：

我们从数组中的第一个元素开始，逐个遍历数组中的每个元素。

当遍历到数组中的元素 q 时，如果 q 能够被 x 整除，则在数组的末尾添加 x 个整数 qx，并开始遍历下一个元素。

否则，停止遍历，数组延伸结束。

注意，后面新增的元素也要被考虑在内，加以处理和判断。

请计算，在数组延伸结束后，数组中所有元素的和。

输入格式
第一行包含整数 T，表示共有 T 组测试数据。

每组数据的第一行包含两个整数 n 和 x。

第二行包含 n 个整数 a1,a2,…,an。

输出格式
每组数据输出一行，一个结果，表示延伸结束后，数组中所有元素的和。

数据范围
1≤T≤100,
1≤n≤105,
2≤x≤109,
1≤ai≤109,
输入保证，所有 T 个 n 的和不超过 105。

输入样例：

2
1 2
12
4 2
4 6 8 2

输出样例：

36
44

样例解释
第一组数据，最终数组为 [12,6,6,3,3,3,3]。

第二组数据，最终数组为 [4,6,8,2,2,2,3,3,4,4,1,1,1,1,1,1]。

---

一、主要思路

需要明白几点

1. 如果能整除就在末尾加上 k个 商
2. 如果不能整除直接退出
   做法: 没有必要在数组末尾一个一个加上商, 可以定义一个结构体,里面存上一个 cnt,代表这个数有几种,下次再被分解的时候直接在cnt的基础上乘上 K

二、实现

代码如下：

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;

typedef long long LL;

struct node
{
    LL val,cnt;
};
int main()
{
    int T;
    cin>>T;
    while(T -- )
    {
        int n, k;
        cin >> n >> k;
        vector<node> vec;
        vec.resize(n);
        for(int i = 0; i < n; i ++)
        {
            int x;
            cin >> x;
            vec[i] = {x, 1};
        }
        for(int i = 0; i < vec.size(); i ++)
        {
            if(vec[i].val % k == 0)
            {
                vec.push_back({vec[i].val / k, k * vec[i].cnt});
            }
            else break;
        }
        LL res = 0;
        for(int i = 0; i < vec.size(); i ++)
        {
            res += vec[i].val * vec[i].cnt;
        }
        cout << res << endl;
        
    }
}