找到多一些，可以写1和0 [英] Find multiple of a number that can be written with 1s and 0s

问题描述

由于数量 N （2'; = N＆LT; = 1000），找到最低非零多个，其中写在基地10与数字0和1只。例如：2 - > 10，3 - > 111，4 - > 100，7 - > 1001，11 - > 11，9 - > 111 111 111

Given the number n (2 <= n <= 1000), find the lowest nonzero multiple of which is written in base 10 with digits 0 and 1 only. Examples: 2 -> 10, 3 -> 111, 4 -> 100, 7 -> 1001, 11 -> 11, 9 -> 111 111 111.

我的想法是不太好：  {/ * N | 2和n | 5 +000（最大的幽灵（2,5）） - >       N | 3 +111* /}

My idea is not very good: {/* n|2 and n|5 +"000"(max for apparition(2,5)) -> n|3 + "111 " */}

我觉得，按照其余部门的号码由数N是格式化0/1。 感谢您的帮助！

I think, follow the remaining division of numbers consist of numbers n which is formatted 0/1. Thanks for your help!

推荐答案

您可以先使用广度搜索。首先enqueing 1 ，因为你的号码必须以 1 ，然后每次提取数 X 从队列，看它是否 N 与否的倍数。如果是的话，你有你的答案，如果没有插入 X * 10 和 X * 10 + 1 队列（按照这个顺序）。

You can use a breadth first search. Start by enqueing 1, since your number must start with a 1, then each time you extract a number x from your queue, see if it's a multiple of n or not. If yes, you have your answer, if not insert x * 10 and x * 10 + 1 in the queue (in that order).

请注意，你实际上并不需要存储的整个字符串 1 和 0 在你的队列：这是不够用 N 和一些辅助信息，可以让你重建的实际字符串存储除法的余数。写回，如果你需要了解更多这方面的细节。

Note that you do not actually have to store the entire strings of 1s and 0s in your queue: it's enough to store the remainder of division by n and some auxiliary information that lets you reconstruct the actual string. Write back if you need more details about this.

这篇关于找到多一些，可以写1和0的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！