E29982: 一种等价类划分问题

hashing, http://cs101.openjudge.cn/practice/29982/

在两个正整数m和n给定的整数范围内（m 小于 n，且不包括m和n）取出各位数字之和均为k的倍数的所有数(k为正整数)，然后将这些数划分成若干个子集合，每个子集合中的元素满足其各位数字之和相等，请输出各个子集合, 其中 n 不大于10000。

每个集合元素按从小到大输出，逗号间隔，如果有多个集合，则输出多行；各位数字之和较小的集合在前面行输出。

例如，m=11, n=35, k=3 则， 12,21,30 这三个数的每位数字之和均为3，且为3的倍数 15,24,33 这三个数的每位数字之和为6，且为3的倍数 18,27 这二个数的每位数字之和为9，也为3的倍数 由于三组数的最小数分别是12,15,18，于是，输出结果应为： 12,21,30 15,24,33 18,27

输入

一行，三个值：m,n,k，以逗号间隔

输出

输出各位数之和为k的倍数的若干行，每一行中，其元素的各位数字和相等，且前面行元素的各位数字之和小于后面行元素的各位数字之和，每行的元素按增序排列，以逗号间隔。

样例输入

11,35,3

样例输出

12,21,30
15,24,33
18,27

提示

hashing

来源

yan

数字最大为 9999 → 最大数字和为 9+9+9+9 = 36。

m, n, k = map(int, input().split(','))
groups = {}

# 注意：题目说“不包括 m 和 n”，所以是 (m, n) → range(m+1, n)
for num in range(m + 1, n):
    s = sum(map(int, str(num)))
    if s % k == 0:  # s 不可能为 0，因为 num ≥ m+1 ≥ 2
        if s not in groups:
            groups[s] = []
        groups[s].append(str(num))

# 按数字和从小到大输出（即 k, 2k, 3k, ... ≤ 36）
t = k
while t <= 36:
    if t in groups:
        print(','.join(groups[t]))
    t += k

m, n, k = map(int, input().split(','))

# 字典：key 为 各位数字之和，value 为 满足条件的数字列表
groups = {}

# 遍历区间 (m, n)
for num in range(m + 1, n):
    s = sum(map(int, str(num)))
    if s % k == 0:  # 数位和是 k 的倍数
        groups.setdefault(s, []).append(num)

# 按数位和从小到大输出
for s in sorted(groups):
    print(','.join(map(str, sorted(groups[s]))))