思路:
每次分解 a[i],总和会增大 a[i]。
循环扫描,扫描到a[i], 如果a[i]能整除k,则a[i]更新为a[i]/k。
用数组 b 保存下a 的原来值。
用s[i]保存增加增加后的各个位置的值,初始和a一样。a[i] 能整除k, s[i] 更新为 s[i] + b[i].
最后求下 s 中元素的总和就行。
注意暴int, 用 long long 保存。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 100010;
LL a[N], b[N],s[N];
int main()
{
int T;
cin >>T ;
while(T--)
{
int n, k;
cin >> n >> k;
for(int i = 0; i < n; i++)
{
cin >> a[i];//保存除k之后的值
b[i] = a[i];//保存原始数组
s[i] = a[i];//保存增加的值
}
int i = 0;
while(a[i] % k == 0)
{
s[i] += b[i];//如果a[i]能整除k,则s[i]增加b[i]
a[i] = a[i]/k;//更新a[i]为除以k后的值
i++;
if(i == n) i = 0;//如果处理到最后,就重头再次处理
}
long long res = 0;
for(int i = 0; i < n; i++) res += s[i];
cout << res << endl;
}
return 0;
}
没必要开一个s数组,res先遍历一遍a数组,把a数组每个数都加上就可以了
是的,可以不开。
%%%