题目理解

我们有一个“奇怪的” K 进制系统：

• 基数是 K
• 每一位数字必须来自给定的集合 {a₁, a₂, ..., a_D}
• 数字可以是负数
• 要表示整数 n 为：d₀ + d₁×K + d₂×K² + ...，其中每个 dᵢ 在给定的数字集合中

如果无解输出 IMPOSSIBLE，否则输出任意一种表示（0 也要至少一位数字）。

关键点

• K 可能很大（最大 10⁶），但数字集合大小 D ≤ 5001
• n 的范围很大（-10¹⁸ 到 10¹⁸）
• Q 很小（≤ 5），可以对每个查询单独处理

思路

我们可以从低位到高位构造表示：

1. 设当前要表示的数是 x
2. 选择一位数字 d，使得 (x - d) 能被 K 整除
3. 然后令 x = (x - d) / K
4. 重复直到 x = 0

为什么这样可行？ 因为 n = d₀ + K × (d₁ + d₂×K + ...)，所以 d₀ 必须满足 d₀ ≡ n (mod K)。

算法步骤

对每个查询 n：

1. 如果 n = 0，直接输出 0
2. 否则：
   • 初始化答案列表
   • 当前值 x = n
   • 重复：
     • 计算需要的余数 r = (x mod K)，调整为非负数
     • 在数字集合中找一个数字 d，使得 d mod K = r
     • 如果找不到，输出 IMPOSSIBLE
     • 否则，把 d 加入答案
     • 更新 x = (x - d) / K
     • 如果 x = 0，停止
   • 反转答案（因为是从低位到高位存的）
   • 输出答案

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

typedef long long ll;

int main() {
    int K, Q, D, M;
    cin >> K >> Q >> D >> M;
    
    vector<int> digits(D);
    for (int i = 0; i < D; i++) {
        cin >> digits[i];
    }
    
    // 预处理每个余数对应的数字
    vector<vector<int>> mod_map(K);
    for (int d : digits) {
        int r = ((d % K) + K) % K;  // 保证余数在 0 到 K-1 之间
        mod_map[r].push_back(d);
    }
    
    while (Q--) {
        ll n;
        cin >> n;
        
        if (n == 0) {
            cout << "0\n";
            continue;
        }
        
        vector<int> result;
        ll x = n;
        bool possible = true;
        
        while (x != 0) {
            // 计算当前需要的余数
            int need_r = ((x % K) + K) % K;
            
            if (mod_map[need_r].empty()) {
                possible = false;
                break;
            }
            
            // 选择第一个可用的数字
            int chosen = mod_map[need_r][0];
            result.push_back(chosen);
            
            // 更新 x
            x = (x - chosen) / K;
        }
        
        if (!possible) {
            cout << "IMPOSSIBLE\n";
        } else {
            // 反转结果，因为我们是从低位开始存的
            reverse(result.begin(), result.end());
            for (int i = 0; i < result.size(); i++) {
                if (i > 0) cout << " ";
                cout << result[i];
            }
            cout << "\n";
        }
    }
    
    return 0;
}

样例验证

样例1

输入：

3 3 3 1
-1 0 1
15
8
-5

输出：

1 -1 -1 0
1 0 -1
-1 1 1

正确。

样例2

输入：

10 1 3 2
0 2 -2
17

输出：

IMPOSSIBLE

正确，因为 17 mod 10 = 7，但数字集合 {0, 2, -2} 中没有模 10 余 7 的数。

复杂度分析

• 每个查询最多 O(log |n|) 步
• 每步 O(1) 查找（因为预处理了）
• 总复杂度：O(Q × log |n|)，非常高效

这个解法利用了模运算的性质，能够快速判断是否存在解并构造出一种表示。