解答
注意到每次增加的元素总和与是等于a[i]的,那么我们就可以看作循环扫描数组,每次将a[i]变为a[i]/x
进一步优化,记录每一个a[i]最多能整除x多少次,设最小值为min,对应索引为index
那么我们可以对数组循环扫描min次,最后一轮扫描,前index-1个元素又再次得到更新
综上,ans = a[0] +.... a[n-1] * min + a[0] + ....a[index-1] 。
前缀和优化一下 ans = sum[n-1] * min + sum[index-1]
代码
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i =a ; i < b ; ++i)
const int maxn = 1e5+1;
using ll = long long int;
ll a[maxn];
ll sum[maxn];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int n,x ; scanf("%d%d",&n,&x);
ll ans = 0;
ll min_ = 0x3f3f3f, index;
rep(i,0,n)
{
scanf("%lld",&a[i]);
sum[i] = ((i==0)? 0 : sum[i-1]) + a[i];
ll cnt = 1 , res = a[i];
while(res % x == 0)
{
res /= x;
cnt++;
}
if(cnt < min_)
{
min_ = cnt;
index = i;
}
ans += a[i];
}
printf("%lld\n",ans*(min_) + ((index == 0)?0:sum[index-1]));
}
}