ARC084B Small Multiple 发表于 2025-02-22 更新于 2025-02-26 分类于 算法竞赛 ， 题 ， AtCoder 阅读次数： 题意 ： 给定整数 。 求 ，使得 在十进制下的数位和最小，输出这个最小值。 。 若 ，则要配上 得到最优方案 。此时 ，故不能直接枚举 。 考虑我们是如何构造一个数 的。 ：数位和不变。 ：若不进位，数位和加一，否则数位和可能减少。 考虑同余最短路，记 表示模 的数中数位和最小的。 连边 ，边权为 。 连边 ，边权为 。 然后跑 即可，答案是 。 复杂度 。