Codeforces #1471B Strange List

문제

https://codeforces.com/problemset/problem/1471/B

걸린 시간

00 : 57 : 15

풀이

C++

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
#define all(c) c.begin(), c.end()
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    fastio;
    int tc;
    cin >> tc;
    while(tc--){
        int n, x;
        cin >> n >> x;
        vector<vector<int>> a(30, vector<int>(n, 0));
        for(int i = 0; i < n; i++){
            cin >> a[0][i];
        }
        for(int i = 1; i < 30; i++){
            bool valid = false;
            for(int j = 0; j < n; j++){
                if(a[i-1][j]%x == 0){
                    a[i][j] = a[i-1][j]/x;
                }
                else{
                    valid = true;
                    break;
                }
            }
            if(valid) break;
        }
        ll ans = 0;
        int c = 1;
        for(int i = 0; i < 30; i++){
            for(int j = 0; j < n; j++){
                int q = a[i][j];
                ans += q*c;
            }
            c *= x;
        }
        cout << ans << "\n";
    }
    return 0;
}

로봇은 배열 a 를 순서대로 탐색하며 x 로 나눠질 수 없는 값이 나올 때 작동을 멈춘다. a 배열의 어떤 수 q 를 x 로 나누는 작업을 한 단계라고 할 때, q/x 값을 x 번 복사하므로 단계마다 x 를 제곱한 수 만큼 값이 생겨나며 단계는 log₂10⁹, 최대 29 개가 존재할 수 있다.

30 * n 크기의 배열에 나눠질 수 없는 값이 나오기 전 까지 x 로 나눈 값을 기록한 후, 단계별로 계산한 값을 합하여 출력하면 된다. pow 함수를 사용하면 좀 더 깔끔했을 것 같다.