Strange List(简单数论/幂次)

题目 题意：给定一个序列 a i a_i ai​和x，现要切分每个序列，如果当前数 q q q能整除x，则往序列添加x个 q / x q/x q/x，接着继续往后处理下一个数，重复这个过程，直到遇到数 q q q不能整除x。问最后新序列的数的总和。 题解：观察该过程，发现添加新数，本质上累加的是原始元素的权值。首先查找这n个数里边，被x整除的最小幂次，遇到该数说明不能继续切分了，会终止程序；确定了最小幂次，则每个数的贡献次数就可知了，再基于此判断哪些数有额外的一次贡献，计算进去即可。

#include
using namespace std;
#define ll long long
const int maxn = 200010;

int n, x;
int a[maxn];
int h[maxn];

int cal(int val) {
	int num = 0;
	while (val % x == 0) {
		val /= x;
		++num;
	}
	return num;
}

int main() {
	
	int t;
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d", &n, &x);
		int mn;
		ll ans = 0, sum = 0;
		for (int i = 0; i