vectorwyx 的博客

vectorwyx 的博客

My left brain has nothing right, my right brain has nothing left.

题解 CF1471B 【Strange List】

posted on 2021-01-06 12:03:22 | under 题解 |

(本篇博客同步于CSDN

如果 $x|q$,设 $t=\frac{q}{x}$,那么 $q$ 会分裂成 $x$ 个 $t$。而如果 $x|t$,那么这 $x$ 个 $t$ 又会分裂出 $x^{2}$ 个 $\frac{t}{x}$……很显然这是一个有终点的循环,每循环一次就会多出 $x^{k}$ 个 $\frac{q}{x^{k}}$。我们把当前循环中 $q$ 分裂出的 $x^{k}$ 个数看做 一个整体,每次循环都会使得数组里的元素和增加 $q$。同时,由于 $q\le 10^{9}$,所以循环次数为 $O(\log_{x}{q})$,这是一个上界为 $30$ 的数,直接模拟这个循环即可。

代码如下:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define ll long long
#define fo(i,x,y) for(register int i=x;i<=y;++i)
#define go(i,x,y) for(register int i=x;i>=y;--i)
using namespace std;

inline int read(){
    int x=0,fh=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-') fh=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=(x<<1)+(x<<3)+ch-'0';
        ch=getchar();
    }
    return x*fh;
}

const int N=1e5+5;
int a[N],cnt[N];

void work(){
    int n=read(),x=read();
    ll ans=0;
    fo(i,1,n) a[i]=read(),cnt[i]=0,ans+=a[i];
    fo(i,1,n){
        int t=a[i];
        while(t%x==0){
            t/=x;
            cnt[i]++;
        }
    }
    int flag=1;
    while(flag){
        fo(i,1,n){
            if(cnt[i]) cnt[i]--,ans+=a[i];
            else{
                flag=0;
                break;
            }
        }
    }
    printf("%lld\n",ans);
    //puts("");
}
int main(){
    int T=read();
    while(T--){
        work();
    }
    return 0;
}