题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin >> t;
while(t--)
{
int n,x;
cin >> n >> x;
long long nums[n + 10];
for(int i = 0;i < n;i ++)cin >> nums[i];
// 扫两遍,第一遍记录下来最近的数取模到第几次就无法被整除num,num_i,num为次数,num_i为索引号
// 第二遍,对num_i之前的数,加和到其取模num + 1次,对num_i及之后的数,加和到其取模num次
int num = 10e6,num_i = 10e6;
for(int i = 0;i < n;i ++)
{
long long a = nums[i];
int times = 0;
while(a%x == 0)
{
a /= x;
times++;
}
if(times < num)
{
num = times;
num_i = i;
}
if(num == 0)break;
}
long long res = 0;
for(int i = 0;i < n;i ++)
{
if(i < num_i)
res += nums[i] * ((num + 1) + 1);
else
res += nums[i] * (num + 1);
}
cout << res << endl;
}
}