P1602 Sramoc 问题【洛谷算法习题】

P1602 Sramoc 问题网页链接P1602 Sramoc 问题题目描述话说员工们整理好了筷子之后就准备将快餐送出了但是一看订单都傻眼了订单上没有留电话号码只写了一个Sramoc ( k , m ) \text{Sramoc}(k,m)Sramoc(k,m)函数。这什么东西什么意思于是餐厅找来了资深顾问团的成员YQSCHQ经过大量的查阅大家获得了一些信息Sramoc ( k , m ) \text{Sramoc}(k,m)Sramoc(k,m)表示用数字0 , 1 , 2 , … , k − 1 0,1,2,\ldots,k-10,1,2,…,k−1组成的正整数中能被m mm整除的最小数。例如k 2 , m 7 k2,m7k2,m7的时候Sramoc ( 2 , 7 ) 1001 \text{Sramoc}(2,7)1001Sramoc(2,7)1001。自然电话号码就是1001 10011001。为了尽快将快餐送出电脑组的童鞋们埋头算起了这个齐葩的号码……输入格式两个整数k , m k,mk,m。输出格式仅一行那个电话号码最小的数。输入输出样例 #1输入 #12 7输出 #11001说明/提示对于100 % 100\%100%的数据2 ≤ k ≤ 10 2\le k\le102≤k≤101 ≤ m ≤ 10 3 1\le m\le 10^31≤m≤103。解题思路本题是BFS 求模意义下的最短数字串问题。将数字串的构造过程视为在模m mm余数状态空间中的搜索每添加一位数字相当于一次状态转移首次到达余数0 00的数字串即为所求的最小正整数。1. 问题等价转化数字串与余数设当前构造的数字串为x xx其模m mm的余数为r x m o d m r x \bmod mrxmodm。在末尾追加一个数字d dd0 ≤ d k 0 \le d k0≤dk后新数字为x ′ x × 10 d x x \times 10 dx′x×10d对应新余数为r ′ ( r × 10 d ) m o d m r (r \times 10 d) \bmod mr′(r×10d)modm目标找到从某个非零首位开始经过若干次追加数字后使余数变为0 00的最短且字典序最小的数字串。首位约束正整数不能以0 00开头因此初始数字只能从1 11到k − 1 k-1k−1中选择。2. 算法实现BFS 枚举余数状态初始化将首位数字1 , 2 , … , k − 1 1,2,\dots,k-11,2,…,k−1分别作为初始数字串计算它们模m mm的余数i % m。如果余数为0 00则已经找到答案否则将这些余数依次入队并记录该余数对应的首位数字dig[余数]父状态标记为− 1 -1−1。BFS 扩展从队列中取出当前余数now。枚举下一位数字i 0 , 1 , … , k − 1 i 0,1,\dots,k-1i0,1,…,k−1计算新余数to (now * 10 i) % m。若to未被访问过则记录其父状态par[to] now数字dig[to] i并标记访问、入队。若to 0说明找到了一个能被m mm整除的数字串立即回溯输出并结束。路径输出从余数0 00开始沿着par数组不断回溯到初始状态-1再逆序输出每一步记录的dig即可得到完整数字串。3. 正确性与最小性最短长度BFS 按层扩展每条边的代价均为1 11添加一位数字因此第一次到达余数0 00的路径一定是长度最短的数字串。字典序最小在扩展下一状态时数字i ii从0 00到k − 1 k-1k−1从小到大枚举因此同一层中的状态按字典序顺序被发现。当多个长度相同且都能到达0 00的数字串存在时BFS 会优先找到字典序最小的那一个。状态去重同一余数只需保留第一次被发现时的最短前缀后续更长或字典序更大的到达方式可以剪枝避免无效扩展。4. 复杂度分析状态数余数只有m mm种m ≤ 10 3 m \le 10^3m≤103。转移规模每个状态最多扩展k kk次k ≤ 10 k \le 10k≤10。时间复杂度O ( k ⋅ m ) O(k \cdot m)O(k⋅m)极小。空间复杂度O ( m ) O(m)O(m)存储vis、par、dig及队列。总结本题利用“数字串拼接等价于余数状态转移”的性质把求最小倍数转化为在余数状态图中求最短路径。BFS 天然保证长度最小按数字升序扩展保证同长度下字典序最小。最终通过父指针回溯输出结果。代码简要说明全局数组vis[15000]记录某个余数是否已访问。par[15000]记录某个余数状态的前驱余数。dig[15000]记录从par[to]到to所添加的数字。BFS 函数若队列非空取出队首now。枚举下一数字i计算to (now * 10 i) % m。若to未访问记录父节点和数字入队。若to 0递归打印路径并换行返回。主函数读入k , m k,mk,m。将首位数字1 11到k − 1 k-1k−1的余数入队并标记。调用bfs()搜索并输出答案。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll k,m;ll vis[15000],par[15000],dig[15000];queuellq;voidprint(ll x){if(x-1)return;print(par[x]);coutdig[x];}voidbfs(){while(!q.empty()){ll nowq.front();q.pop();for(ll i0;ik;i){ll to(now*10i)%m;if(!vis[to]){vis[to]1;dig[to]i;par[to]now;q.push(to);if(to0){print(to);cout\n;return;}}}}}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);cinkm;memset(par,-1,sizeof(par));for(ll i1;ik;i){q.push(i%m);vis[i%m]1;dig[i%m]i;}bfs();return0;}