找呀找呀找规律
首先你要知道
如果这个a[i]可以被k整除t次,那么它最多可以出现t+1次
但是呢,一旦遇到猪队友,所有人就被取消继续重复出现的资格了
所以我们首先看看猪队友是谁
我们在第二个样例发现猪队友是6
真坑啊出现了两次,想要出现第三次的时候失败了
那么8可以出现4次的但是因为在它后面所以只出现了两次
而4可以出现三次,因为在6前面所以提前做了三次出现尝试并且过了
所以4出现了三次
那么我们知道
猪队友能出现t次的话
猪队友前的队友最多可以出现t+1次
后面的队友最多只能出现t次
#include<bits/stdc++.h>
using namespace std;
const int N5 = 1e5 + 10;
int n, t, k, a[N5], cnt[N5], m, mi;
int main()
{
cin >> t;
while(t --)
{
cin >> n >> k;
m = 2e9;
long long res = 0;
for(int i = 1; i <= n; i ++)
{
cin >> a[i];
cnt[i] = 1;
int b = a[i];
while(b % k == 0) b /= k, cnt[i] ++;
if(cnt[i] < m)
{
m = cnt[i];
mi = i;
}
}
for(int i = 1; i < mi; i ++) res += (long long)min(m + 1, cnt[i]) * a[i];
for(int i = mi; i <= n; i ++) res += (long long)min(m, cnt[i]) * a[i];
cout << res << endl;
}
}