密码分配（Password Crack）

密码分配

题目描述

有 n 台破解器，字符集 S 长度为 k，密码长度为 m。总共有 k^m 个密码，按 S 定义的字典序排列。每台破解器处理连续的一段密码，要求：

• 所有密码都被处理
• 工作量均衡，最大与最小工作量差不超过 1

解题思路

1. 计算总密码数

total = k^m

2. 均匀分配

base = total // n        # 每台基础数量
remainder = total % n    # 前 remainder 台多处理 1 个

3. 索引转密码（k进制转换）

将索引转换为 k 进制，每位对应字符集 S 中的字符。

def idx_to_password(idx):
    res = []
    for _ in range(m):
        res.append(s[idx % k])  # 取余得到当前位字符
        idx //= k               # 右移一位
    return ''.join(reversed(res))

代码实现

def idx_to_password(idx):
    res = []
    for _ in range(m):
        res.append(s[idx % k])
        idx //= k
    return ''.join(reversed(res))

n, m = map(int, input().split())
s = input().strip()

k = len(s)
total = k ** m
lenth_for_machine = total // n
remainder = total % n
a = 0
for i in range(n):
    len_i = lenth_for_machine
    if i < remainder:
        len_i += 1
    b = a + len_i
    print(idx_to_password(a), idx_to_password(b - 1))
    a = b

时间复杂度

• 计算总密码数：O(log k^m)（幂运算）
• 索引转密码：每次 O(m)，共 n 次
• 总计：O(n × m)

空间复杂度

• 输出列表：O(n × m)（存储 n 个密码）
• 其他：O(1)