题目描述
给定一个初始长度为 $n$ 的数组 $a$ 以及一个整数 $x$。
我们现在要对数组 $a$ 进行延伸,具体方法如下:
我们从数组中的第一个元素开始,逐个遍历数组中的每个元素。
当遍历到数组中的元素 $q$ 时,如果 $q$ 能够被 $x$ 整除,则在数组的末尾添加 $x$ 个整数$ q/x$,并开始遍历下一个元素。
否则,停止遍历,数组延伸结束。
注意,后面新增的元素也要被考虑在内,加以处理和判断。
请计算,在数组延伸结束后,数组中所有元素的和。
输入格式
第一行包含整数 $T$,表示共有 $T$ 组测试数据。
每组数据的第一行包含两个整数 $n$ 和 $x$。
第二行包含 $n$ 个整数 $a$1,$a$2,…,$a$n。
输出格式
每组数据输出一行,一个结果,表示延伸结束后,数组中所有元素的和。
数据范围
$1≤T≤100$
$1≤n≤10^5$
$2≤x≤10^9$
$1≤ai≤10^9$
输入保证,所有 $T$ 个 $n$ 的和不超过 $10^5$。
输入样例:
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]$。
代码&思路
#include<iostream>
using namespace std;
int w[100010];
int main()
{
int m;
cin>>m;
while(m--)
{
int n,x;
cin>>n>>x;
for(int i=1;i<=n;i++)
{
cin>>w[i];
}
long long sum=0,psum=0;//总和,一段的和
int cnt=10000000;
for(int i=1;i<=n;i++)
{
sum+=w[i];
int c=0;
for(int j=w[i];j%x==0;j/=x)
{
c++;//每个数可以遍历的次数
}
if(c<cnt)//求最少的次数
{
cnt=c;
psum=sum-w[i];//求一段的和,即,到最后只能遍历的那一段的和
}
}
cout<<sum*(cnt+1)+psum<<endl;//总数
}
return 0;
}