Я наткнулся на вопрос на сайте Code Review , что кажется интересным. Я думаю, что OP делает это неправильно, но не может быть уверен ... Так что давайте решим это для него! (написать программу, а не функцию / процедуру)

Ввод (стандартный или аналогичный):

Целое число xв десятичной записи. Это больше чем 1 и меньше чем 2 ^ 31.

Выход (стандартный вывод или аналогичный):

Целое число yв десятичной записи. Продукт x * yв десятичном представлении должен содержать только цифры 0 и 1. Это должно быть минимальное такое число больше 0.

Примечание: вывод не ограничен - если минимальное значение yсоставляет около 10 ^ 100, ваша программа должна вывести все свои 100 цифр (я не знаю, существует ли разумный предел, например 2 ^ 64, y- не удалось его решить ).

Ваша программа должна завершиться за разумное время (1 секунда или 1 час? - что-то в этом роде) для всех xв диапазоне.

Бонус:

Если ваша программа не имеет ограничений на размер входных данных (кроме ОЗУ) и имеет полиномиальную сложность, умножьте количество байтов вашей программы на 0.8и округлите вниз.

Пример: ввод 2; выход 5, потому что 2 * 5 = 10

Пример: ввод 21; выход 481, потому что 21 * 481 = 10101

Отказ от ответственности: я не несу ответственности за вопрос на сайте Code Review. В случае любого несоответствия, только описание выше должно рассматриваться как правильная спецификация.

OEIS A079339

Pyth, 9 байт

f!-`*TQ10

демонстрация

Для каждого кратного числа преобразуйте в строку, вычтите цифры 10(используя в этом случае удобную для Pyth int для str) и затем логически отрицайте результат, прерывая поиск только тогда, когда найдено правильное кратное число.

Бонусное решение, 10 байт:

f.xi`*TQ2Z

Это решение фактически проверяет, может ли строковое представление числа рассматриваться как двоичное число ( i ... 2), и завершается, когда при этой попытке не выдается ошибка.

Python 2, эффективное решение, 99

n=input()
d={n:0}
k=1
while min(d):[d.setdefault((x+k)%n,d[x]+k)for x in set(d)];k*=10
print d[0]/n

Спасибо Sp3000 за некоторые советы по игре в гольф.

Я призываю всех остальных опубликовать (в своих собственных ответах), сколько времени потребуется, чтобы получить результат для ввода 72или 99:) Если они действительно быстрые, попробуйте что-то вроде 79992следующего (все еще <1 сек. Здесь).

Объяснение:

Я думал, что в этом нет необходимости (так как код достаточно читабелен), но я получил запрос, так что вот оно:

Первая идея состоит в том, что двоичное число представляет собой сумму 1 или более различных степеней 10. Поэтому мы можем пытаться добавлять различные степени 10 по-разному, пока не получим остаток 0.

Если мы делаем это наивно, это то же самое, что генерировать все двоичные числа и проверять их. Но многие остатки останутся прежними. Лучший способ - записать только наименьшее число, которое дало определенный остаток, и последовательно прибавлять 10 к числу, которое мы записали. Это то, что делает программа.

dэто словарь / карта, где ключи - это остатки, а значения - двоичные числа с этим остатком. Инициал n:0- это особый случай: он должен быть 0:0таким, чтобы мы могли начать добавлять к нему полномочия, но алгоритм останавливается при поиске ключа 0, поэтому я использовал nвместо этого, что гарантированно будет иметь тот же эффект и не мешать другим значениям.

Затем мы начинаем прибавлять степени 10 (хранятся в k) ко всем существующим числам и записывать остатки. Мы добавляем kк остатку: (x+k)%nи к числу: d[x]+kи записываем его, только если это новый остаток:, d.setdefault(…)затем переходим к следующей степени: k*=10и повторяем, пока не получим ключ 0:while min(d)

В конце d[0]дает двоичное число с остатком 0 mod n, поэтому мы делим его nна полученное решение.

Примечание: программу можно сделать более эффективной, избегая больших чисел (запись показателей степени, а не степеней 10 и вычисление остатков степеней от предыдущих значений), но это код гольф, так что ...

На самом деле, здесь я написал более быструю версию:

n=input()
d={n:0}
k=1
b=0
while 0not in d:
 for x in list(d):d.setdefault((x+k)%n,b)
 k=(k*10)%n;b+=1
x=10**d[0]
while x%n:x+=10**d[n-x%n]
print x/n

Python 2, 47 байт

n=a=input()
while'1'<max(str(a)):a+=n
print a/n

Отслеживает введенный номер nи текущий множитель a. Когда aвыглядит как двоичный файл, выведите соотношение a/n. Чтобы проверить, что число состоит из 0's' и 1's', мы сравниваем максимальное значение char в его строковом представлении с '1'.

Пользы str(a) вместо того, `a`чтобы избежать длинных, заканчивающихся на L. К сожалению, 'L'больше, чем '1'.

Perl, 27 байт

#!perl -p
1while($_*++$\)=~/[2-9]/}{

Считая Шебанг как единое, ввод берется из стандартного ввода.

Образец использования

$ echo 2 | perl dec-bin.pl
5

$ echo 21 | perl dec-bin.pl
481

$ echo 98 | perl dec-bin.pl
112245

Perl, 25 байт

#!perl -p
eval'0b'.++$\*$_||redo}{

Двухбайтовое улучшение @skmrx .

Вместо проверки на регулярное выражение вместо этого делается попытка оценить продукт как двоичный литерал. При неудаче он переходит к следующему. Типичноoct функция используется для этой цели, но она молча обрезает недопустимые цифры, что бесполезно в этой задаче.

Perl, 40 байт

#!perl -p
1while($b=sprintf"%b",++$i)%$_;$_=$b/$_

Гораздо более эффективное решение. Мы перебираем двоичные представления, интерпретируем их как основание 10, а затем проверяем на делимость. Время выполнения для всех значений до 100 пренебрежимо мало.

Образец использования

$ echo 72|perl dec-bin.pl
1543209875

$ echo 99|perl dec-bin.pl
1122334455667789

Javascript, 43 байта

Это оказалось короче, чем я думал. Это в основном увеличивается yдо 1 до y * (input number) = (binary-looking number). Очевидно, совершенно неэффективно.

for(x=prompt(y=0);!+('0b'+x*++y););alert(y)

Javascript (более эффективное решение), 53 байта

Этот шаг увеличивается yв двоичном формате до y / (input number) = (number without a remainder). Тогда это выводит (number without a remainder).

for(x=prompt(y=1);(z=y.toString(2))%x;y++);alert(z/x)

Javascript (еще более эффективное решение), 76 байт

Этот объединяет оба предыдущих метода, описанных выше. Он проверяет приращения yдо тех пор, пока y * (input number) = (binary-looking number)( либо означает, что выходные данные y), или ИЛИ y / (input number) = (number without a remainder)(означает, что выходные данные есть (number without a remainder)).

for(x=prompt(y=a=0);!a;a=+('0b'+x*++y)?y:(z=y.toString(2))%x?0:z/x);alert(a)

Haskell, 72 70 64 60 58 байт

main=do x<-readLn;print$[y|y<-[1..],all(<'2')$show$x*y]!!0

Редактировать: @ Ян Дворак помог мне сэкономить 4 байта.

Редактировать: @BlackCap сохранил 2 байта, переключившись на doнотацию. Благодарность!

Python 2, 67 65 63 60 байт

a=input();b=1
while set(`a*b`)&set('23456789'):b+=1
print b

Спасибо Status за 2 байта и Shebang за 5 байтов!

JavaScript (ES6) 222 250

Использование математики произвольной точности (работа со строками десятичных цифр)

Это может быть немного больше (сделано), но мне нравится тот факт, что он не ограничивается стандартными числами JS (17 десятичных цифр точности) и что это быстро.

Попробуйте запустить приведенный ниже фрагмент в браузере, совместимом с EcmaScript 6. Время приемлемо до 9998 - не пытайтесь 9999 и будьте терпеливы с 999.

// As a complete program with I/O via popup  
for(n=+prompt(a=[0],q=[t=1]);t;){for(c=1,t=i=0;i<a.length;i++)a[i]=a[i]&c?0:a[i]|c?(c=0,t+=q[i],1):c=0;c&&(a[i]=c,t+=q[i]=q[i-1]*10%n);t%=n}a.reverse().map(a=>(z+=[a],d=z/n|0,z%=n,r||d?r+=d:0),r='',z=0);alert([r,a.join``])

// As a testable function
f=n=>{
  for(a=[0],q=[t=1];t;)
  {
    for(c=1,t=i=0;i<a.length;i++)
      a[i]=a[i]&c?0:a[i]|c?(c=0,t+=q[i],1):c=0
    c&&(a[i]=c,t+=q[i]=q[i-1]*10%n);
    t%=n
  }  
  a.reverse().map(a=>(z+=[a],d=z/n|0,z%=n,r||d?r+=d:0),r='',z=0)
  return [r,a.join``]
}

// Test and timing
out = x => O.innerHTML += x + '\n'

setTimeout(_=>{
;[1,2,10, 21, 23, 98, 72, 9, 99, 999]
.forEach((test,i) => { 
  var t0 = ~new Date  
  var result = f(test)
  out('n='+test+' '+result+' time(ms) ' + (t0-~new Date))
})},100)  

<pre id=O>Timing test cases ...
</pre>

Более читаемый

Это первая версия с модулем и длинным делением в качестве отдельных функций.

// function M - Modulus with arbitrary precision - a is a string of decimal digits
M = (a, b, q = 1, t = 0, j = a.length) => {
  while (j--) + a[j] ? t += q : 0, q = (q * 10) % b;
  return t % b
}

// function D - Long division with arbitrary precision - a is a string of decimal digits
D = (a, b, r = '', z = 0) => [...a].map(a => (z += a, d = z / b | 0, z %= b, r || d ? r += d : 0)) && r

// Testable function 
f = n => {
  for (i = 0; ++i < 1e7 && (z = M(v = i.toString(2), n)););
  return z ? ['big'] : [D(v, n), v]
}

Perl, 45 байт

do{$a++}while($a*($b||=<>))=~/[2-9]/;print$a;

Pyth, 10 байт

f<eS`*TQ`2

Запустите код.

Порт моего Python-ответа , взявший у Малтисена использование fдля поиска первого положительного числа, удовлетворяющего условию.

PHP, 50 байт

while(preg_match('/[^01]/',$argv[1]*++$y));echo$y;

Некоторые тестовые случаи

1 > 1
2 > 5
12 > 925
21 > 481

CJam, 19 17 16 байтов

li:V!{)_V*sAs-}g

Попробуйте онлайн

Решение грубой силы, пробуя значения последовательно, пока не будет найдено одно условие.

Последняя версия экономит 2 байта благодаря использованию Asвместо "01"построения строки, содержащей 0и 1, как предлагает @aditsu. Полное предлагаемое решение в комментарии сохраняет еще один байт, но выглядит он совсем не так, как мой, поэтому я не хотел публиковать его под своим именем.

И еще 1 байт, сохраненный @Dennis.

Объяснение:

li      Get input and convert to int.
:V      Save it in variable V.
!       Negate the value. Since we saved it in V, we don't need it on the stack anymore.
        But we need 0 on the stack as the start value for y. This conveniently
        accomplishes both with a single operator, since the input is guaranteed to be
        larger than 0.
{       Loop over y.
  )       Increment y.
  _       Copy it.
  V*      Multiply with input in variable V.
  s       Convert to string.
  As      Push the string "10", as the number 10 converted to a string .
  -       Remove 0 and 1 digits. This will result in an empty list if there were only
          0 and 1 digits. The empty list is falsy, and will terminate the loop.
}g      End loop.

Python 3 2, 101 76 байт

-25 байт благодаря @aditsu

почти так же эффективно, как решение @ aditsu

99 -> 0.436 Seconds
72 -> 0.007 Seconds

b,m,n=1,1,input()
while b%n:
 b=int("{0:b}".format(m))
 m+=1
print b/n

Вместо того, чтобы пытаться перебирать мультипликаторы в возрастающем порядке, я пытаюсь перебрать продукты, которые я генерирую в «двоичной» форме.

Java, 213 байт

import java.math.*;class P{public static void main(String[]a){BigInteger b=new java.util.Scanner(System.in).nextBigInteger(),c,d=c=b.ONE;while(!(b.multiply(c)+"").matches("[01]+"))c=c.add(d);System.out.print(c);}}

Пользы BigInteger s и как таковой имеет (для всех разумных намерений и целей) неограниченный размер ввода. Не уверен насчет сложности, хотя, это зависит от скорости роста нашей функции здесь.

Спасибо geobits и ypnypn за сохранение нескольких байтов.

C 3675 байт

Так долго для Code Golf ...

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>

#define min_n 1
#define max_n 10000

unsigned *mod_list; // list of mods to check
unsigned mod_list_length; // number of mods to check
char *graph; // for each mod, the power of 10 that gives it

void BuildGraph(unsigned n)
{
    unsigned mod10 = 10 % n;
    int pow = 1;

    memset(graph, 0, n);
    if (n == 1)
        return;
    mod_list[0] = 0; // mod 0 - no path coming to it yet
    mod_list[1] = 1; // mod 1 - 10^0 coming to it
    mod_list_length = 2;
    while (graph[0] == 0)
    {
        // We are going to change mod_list_length by adding new nodes.
        // This should not affect the set of nodes we check, so save its old value.
        unsigned mod_list_limit = mod_list_length;
        for (unsigned i = 0; i < mod_list_limit; ++i)
        {
            unsigned mod = mod_list[i] + mod10;
            if (mod >= n)
                mod -= n;
            if (graph[mod] == 0 && mod != 1) // new node?
            {
                graph[mod] = pow; // record the power of 10 with which we come to this node
                mod_list[mod_list_length++] = mod; // add it to the list of nodes
                if (mod == 0) // found the path to 0?
                    return; // stop calculating
            }
        }
        mod10 = (unsigned long long)mod10 * 10 % n; // go to next power of 10
        ++pow;
    }
}

void PrintPath(unsigned n, char *out)
{
    // Going to output powers of 10 in descending order
    unsigned mod = 0; // start at node 0
    int prev_pow = graph[mod] + 1; // happens to be an acceptable initialization
    do {
        int pow = graph[mod];
        while (--prev_pow > pow) // output the proper number of 0-digits
            *out++ = '0';
        *out++ = '1'; // output the digit 1, corresponding to current power of 10
        if (pow == 0)
            break;
        unsigned mod10 = 1;
        for (int p = 0; p < pow; ++p)
            mod10 = (unsigned long long)mod10 * 10 % n;
        mod = (mod + n - mod10 % n) % n; // go to the preceding node
    } while (mod != 0);
    while (--prev_pow >= 0) // output the proper number of 0-digits
        *out++ = '0';
    *out++ = 0;
}

// The long division algorithm
void DivideAndPrint(char *product, unsigned n, FILE* file)
{
    unsigned long long temp = 0;
    int print = 0;
    while (*product != '\0')
    {
        temp = temp * 10 + *product++ - '0';
        if (temp >= n)
            print = 1;
        if (print)
        {
            unsigned quotient = (unsigned)(temp / n);
            unsigned remainder = temp % n;
            fputc('0' + quotient, file);
            temp = remainder;
        }
    }
    fputc('\n', file);
    assert(temp == 0); // if not divisible, there is a bug somewhere
}

void Calc(unsigned n, FILE* file)
{
    char result[99];
    BuildGraph(n);
    PrintPath(n, result);
    DivideAndPrint(result, n, file);
}

int main(int argc, char* argv[])
{
    unsigned n;

    if (argv[1])
    {
        FILE* file = fopen(argv[1], "wt");
        mod_list = calloc(max_n, sizeof(int));
        graph = calloc(max_n, 1);
        clock_t before = clock();
        for (n = min_n; n <= max_n; ++n)
        {
            Calc(n, file);
        }
        clock_t after = clock();
        fprintf(stderr, "Time: %f\n", (after - before) / (double)CLOCKS_PER_SEC);
    }
    else
    {
        scanf("%u", &n);
        mod_list = calloc(n, sizeof(int));
        graph = calloc(n, 1);
        Calc(n, stdout);
    }
}

Запуск без параметров командной строки - она получает nот stdinи выводит результат stdout. Запустите с именем файла - он записывает результаты n = 1...10000в этот файл и измеряет время.

Производительность за 1 ... 10000: 140 мс

Этот код использует алгоритм, предложенный aditsu , реализованный на C для скорости. Я не приложил усилий, чтобы поиграть в гольф, поэтому код будет легче читать.

Я реализовал это сначала в C ++, используя std::mapдля записи результатов поиска, и это было довольно медленно. Однако ключи mapявляются последовательными целыми числами (я называю их mods, потому что они представляют числа по модулю n), поэтому естественно использовать массив - поэтому я переписал его на C.

Дополнительная оптимизация касается значений отображения - во избежание хранения большого целого числа для каждого modя сохраняю там только наибольшую степень 10 - достаточно информации, чтобы перейти к предыдущему mod. Таким образом, массив - это действительно поисковое дерево / граф. Когда поиск прибывает mod = 0, отслеживание узлов дерева назад к корню дает полномочия 10 в порядке убывания.

Так как поиск обычно останавливается довольно быстро, и посещается только небольшая часть узлов, мне нужен список активных узлов. Он реализован в виде массива mod_listс длиной mod_list_length.

Немного статистики во время выполнения (на машине с 16 ГБ ОЗУ, что кажется важным для больших n, потому что программа выделяет 5nбайты памяти):

• Ввод 99999999- 2 секунды
• Ввод 999999999- 27 секунд (результат 111111111222222222333333333444444444555555555666666666777777777888888889- вероятно, самый большой возможный результат для 32-разрядных целых)
• Ввод 2147483647- 26 секунд (результат есть 4661316525084584315813)
• Ввод 1999999998- 52 секунды (вероятно, самое длинное время выполнения для 32-разрядных целых чисел)

C ++ 11, много байтов, очень быстро, вау (1,5 с на 1999999998, 0,2 с на 1… 10000)

(Гольф-версия Python ниже.)

Мы начнем с концепции, несколько похожей на решение aditsu, где мы индуктивно создаем коллекцию модульных остатков, достижимых за n шагов. Но вместо того, чтобы ждать, пока мы не найдем остаток 0, мы проверяем два найденных остатка a и b, так что a · 10 ^ n + b = 0. Такой подход к встрече в середине сокращает вдвое глубину дерева поиска, поэтому намного быстрее на больших входах и использует намного меньше памяти.

Некоторые тесты:

$ echo 99999999 | \time ./decbin
1111111122222222333333334444444455555555666666667777777788888889
0.18user 0.01system 0:00.20elapsed 99%CPU (0avgtext+0avgdata 69360maxresident)k
0inputs+0outputs (0major+16276minor)pagefaults 0swaps
$ echo 999999999 | \time ./decbin
111111111222222222333333333444444444555555555666666666777777777888888889
1.22user 0.04system 0:01.27elapsed 100%CPU (0avgtext+0avgdata 434776maxresident)k
0inputs+0outputs (0major+37308minor)pagefaults 0swaps
$ echo 2147483647 | \time ./decbin
4661316525084584315813
0.00user 0.00system 0:00.01elapsed 72%CPU (0avgtext+0avgdata 5960maxresident)k
0inputs+0outputs (0major+1084minor)pagefaults 0swaps
$ echo 1999999998 | \time ./decbin
555555556111111111666666667222222222777777778333333333888888889444444445
1.42user 0.08system 0:01.50elapsed 100%CPU (0avgtext+0avgdata 544140maxresident)k
0inputs+0outputs (0major+38379minor)pagefaults 0swaps
$ \time ./decbin 10000.out
0.19user 0.00system 0:00.20elapsed 100%CPU (0avgtext+0avgdata 3324maxresident)k
0inputs+264outputs (0major+160minor)pagefaults 0swaps

Код:

#include <algorithm>
#include <boost/iterator/transform_iterator.hpp>
#include <fstream>
#include <list>
#include <iostream>
#include <string>
#include <utility>
#include <vector>

using namespace boost;
using namespace std;

static inline bool cmp_first_partnered(pair<int, pair<int, int>> a,
                                       pair<int, pair<int, int>> b) {
  return a.first < b.first;
}
static inline bool eq_first_partnered(pair<int, pair<int, int>> a,
                                      pair<int, pair<int, int>> b) {
  return a.first == b.first;
}

static pair<int, int> retrace(int modulus, int place, pair<int, int> state,
                              list<vector<int>>::iterator i,
                              list<vector<int>>::iterator j, string &ret) {
  if (i == j)
    return state;
  state = retrace(modulus, (place * 10LL) % modulus, state, next(i), j, ret);
  int remainder = state.first;
  long long k = state.second * 10LL;
  if (!binary_search(i->cbegin(), i->cend(), remainder)) {
    remainder = ((long long)remainder + modulus - place) % modulus;
    k += 1;
  }
  int digit = k / modulus;
  if (digit != 0 || ret.size())
    ret += '0' + digit;
  return make_pair(remainder, k % modulus);
}

static void mult(int modulus, int x, int y,
                 vector<pair<int, pair<int, int>>>::iterator i,
                 vector<pair<int, pair<int, int>>>::iterator j) {
  if (y - x == 1) {
    for (auto k = i; k != j; k++)
      k->first = (k->first * 10LL) % modulus;
    return;
  }

  int z = (x + y) / 2;
  vector<pair<int, pair<int, int>>>::iterator k = lower_bound(
      i, j, make_pair(int(((long long)modulus * z + 9) / 10), make_pair(0, 0)));
  mult(modulus, x, z, i, k);
  mult(modulus, z, y, k, j);
  inplace_merge(i, k, j,
                [](pair<int, pair<int, int>> a, pair<int, pair<int, int>> b) {
                  return make_pair(a.first, a.second.second) <
                         make_pair(b.first, b.second.second);
                });
}

static string go(int modulus) {
  if (modulus == 1)
    return "1";

  int sequence = 1;
  list<vector<int>> v = {{0}};
  vector<pair<int, pair<int, int>>> partnered;
  int place = 1;
  while (true) {
    v.emplace_back(v.rbegin()->size() * 2);
    vector<int> &previous = *next(v.rbegin()), &current = *v.rbegin();

    auto offset = [modulus, place, sequence](int a) {
      return (a + (long long)place) % modulus;
    };
    auto old_mid =
        lower_bound(previous.cbegin(), previous.cend(), modulus - place),
         new_mid = lower_bound(previous.cbegin(), previous.cend(), place);
    current.resize(
        set_union(new_mid, previous.cend(),
                  make_transform_iterator(previous.cbegin(), offset),
                  make_transform_iterator(old_mid, offset),
                  set_union(previous.cbegin(), new_mid,
                            make_transform_iterator(old_mid, offset),
                            make_transform_iterator(previous.cend(), offset),
                            current.begin())) -
        current.begin());

    int place2 = modulus - (long long)place * place % modulus;
    auto offset_partnered = [modulus, place, place2,
                             sequence](pair<int, pair<int, int>> a) {
      return make_pair((a.first + (long long)place2) % modulus,
                       make_pair((a.second.first + (long long)place) % modulus,
                                 sequence + a.second.second));
    };
    auto old_mid_partnered =
        lower_bound(partnered.cbegin(), partnered.cend(),
                    make_pair(modulus - place2, make_pair(0, 0))),
         new_mid_partnered = lower_bound(partnered.cbegin(), partnered.cend(),
                                         make_pair(place2, make_pair(0, 0)));
    vector<pair<int, pair<int, int>>> next_partnered(partnered.size() * 2 + 1);
    auto i =
        set_union(partnered.cbegin(), new_mid_partnered,
                  make_transform_iterator(old_mid_partnered, offset_partnered),
                  make_transform_iterator(partnered.cend(), offset_partnered),
                  next_partnered.begin(), cmp_first_partnered);
    if (new_mid_partnered == partnered.cend() ||
        new_mid_partnered->first != place2)
      *i++ = make_pair(place2, make_pair(place, sequence));
    next_partnered.resize(
        set_union(new_mid_partnered, partnered.cend(),
                  make_transform_iterator(partnered.cbegin(), offset_partnered),
                  make_transform_iterator(old_mid_partnered, offset_partnered),
                  i, cmp_first_partnered) -
        next_partnered.begin());
    partnered.swap(next_partnered);

    sequence += previous.size();

    place = (place * 10LL) % modulus;

    mult(modulus, 0, 10, partnered.begin(), partnered.end());
    partnered.resize(
        unique(partnered.begin(), partnered.end(), eq_first_partnered) -
        partnered.begin());

    auto with_first = [](int a) { return make_pair(a, make_pair(a, 0)); };

    vector<pair<int, pair<int, int>>> hits;
    set_intersection(partnered.cbegin(), partnered.cend(),
                     make_transform_iterator(current.cbegin(), with_first),
                     make_transform_iterator(current.cend(), with_first),
                     back_inserter(hits), cmp_first_partnered);

    if (hits.size()) {
      pair<int, pair<int, int>> best = *min_element(
          hits.begin(), hits.end(),
          [](pair<int, pair<int, int>> a, pair<int, pair<int, int>> b) {
            return a.second.second < b.second.second;
          });
      string ret = "";
      pair<int, int> state =
          retrace(modulus, 1, make_pair(best.second.first, 0), v.begin(),
                  prev(v.end()), ret);
      retrace(modulus, 1, make_pair(best.first, state.second), v.begin(),
              prev(v.end()), ret);
      return ret;
    }
  }
}

int main(int argc, const char *argv[]) {
  ios_base::sync_with_stdio(false);
  if (argc >= 2) {
    ofstream ofs(argv[1]);
    for (int modulus = 1; modulus <= 10000; modulus++)
      ofs << go(modulus) << '\n';
  } else {
    int modulus;
    cin >> modulus;
    cout << go(modulus) << '\n';
  }
  return 0;
}

Python, 280 байт (8,6 секунды на 1999999998 с PyPy)

n=input()
if n<2:print 1;exit()
d={0:0}
l=[]
k=1
b=x=y=0
while 1:
 for a in[0]+l:
  m=(a+k)%n
  if m not in d:l.append(m);d[m]=b
 k=(k*10)%n;b+=1
 for a in l:
  if(-k*a)%n in d:
   while(a-x)%n:x+=10**d[(a-x)%n]
   while(-y-k*a)%n:y+=10**d[(-y-k*a)%n]
   print(10**b*x+y)/n;exit()

Mathematica 115 байтов

p=Drop[Union[FromDigits/@Flatten[Table[Tuples[{0,1},{k}],{k,2,12}],1]],2];
i=Input[];FirstCase[p,x_/;Divisible[x,i]]

Java 156 байт

public class P{public static void main(String[]a){long x=Long.valueOf(a[0]),y;for(y=2;!(""+x*y).replaceAll("1|0","").isEmpty();y++);System.out.println(y);}}

Огромное спасибо адицу :)

Pyth - 12 11 байт

Использует фильтр с числовым аргументом, чтобы получить первое натуральное число, которое соответствует предикату, по умолчанию 1, что мы и хотим. Поочередно diff, чтобы проверить, если только нули и единицы.

f!-j*QT10U2

Тестовый пакет .

R, 45 байт

x=scan();y=2;while(grepl("[2-9]",x*y))y=y+1;y

Использование:

> x=scan();y=2;while(grepl("[2-9]",x*y))y=y+1;y
1: 2
2: 
Read 1 item
[1] 5
> x=scan();y=2;while(grepl("[2-9]",x*y))y=y+1;y
1: 21
2: 
Read 1 item
[1] 481
> x=scan();y=2;while(grepl("[2-9]",x*y))y=y+1;y
1: 42
2: 
Read 1 item
[1] 2405

Джава, 198 193 181 байт

Спасибо @aditsu за сокращение 5 байтов и увеличение диапазона тестируемых чисел!

Обратите внимание, что некоторые значения зацикливаются отрицательно из-за того, что Java анализирует целые числа. BigInteger мог обойти это, но бонус был просто менее ценным.

Я знаю, что не собираюсь побеждать, но я надеюсь, что это вдохновит других, более короткие ответы.

class A {public static void main (String [] a) {for (long i = 1 ;; i ++) {try {long b = Long.parseLong (a [0]); if (b * i <0) break; Long.parseLong (b * i + "", 2); System.out.println (i);} catch (Exception e) {}}}}

Ungofled:

класс А {
   public static void main (String [] a) {
      for (long i = 1 ;; i ++) {// бесконечный цикл, начинающийся с 1
         try {// если выдается ошибка при попытке разобрать как двоичный файл, перезапустите при добавлении 1 к i
            long b = Long.parseLong (a [0]); // На потом - объявить было короче, чем использовать дважды
            если (б * я <0) перерыв; // Выход из программы, если мы зациклились.
            Long.parseLong (б * я + "", 2); // Умножим и посмотрим, можно ли его передать как двоичное число, в противном случае выведите ошибку и вернитесь к началу цикла
            System.out.println (б); // Распечатай
         } catch (Exception e) {} // ничего не делать на catch
      }
   }
}

C 107 101 байт ( 105 99 байт для 32-бит)

Существует явный недостаток ответов в C на коде гольф. Действительно, C не лучший выбор для написания самой маленькой программы, но это не так уж и плохо:

main(d,b){char s[9];gets(s);for(b=atoi(s);sprintf(s,"%d",b*d),strspn(s,"01")[s];d++);printf("%d",d);}

Вы можете обойтись без #include, но тогда все определения функций будут неявными. Основным недостатком является то, что это вызывает предположение, что все функции возвращают целые числа. Это проблема на 64-битных машинах для функций, которые фактически возвращают указатель. Если вы работаете на 32-битной машине, 2 байта могут быть сброшены с помощью вышеуказанного решения:

main(d,b){char s[9];for(b=atoi(gets(s));sprintf(s,"%d",b*d),strspn(s,"01")[s];d++);printf("%d",d);}

Несколько более читаемая версия:

int main()
{
  char s[9];
  gets(s);
  int d = 1;
  int b = atoi(s);
  for (; sprintf(s, "%d", b * d), strspn(s, "01")[s]; d++);
  printf("%d", d);
}

Время C # около 5 секунд (от 1 до 10000)

В соответствии с просьбой, здесь есть программа C # для игры в гольф, отвечающая на первоначальный вызов. Ввод в качестве аргумента командной строки, вывод в консоль.

using System;using System.Collections.Generic;using System.Numerics;using System.Linq;
class P{static void Main(string[] a){int m,n=int.Parse(a[0]);var d=new Dictionary<int,long>();long b;int h;
for(d[n]=0,b=h=1;;b*=2,h=(h*10)%n)foreach(int k in d.Keys.Reverse())if(!d.ContainsKey(m=(h+k)%n)){
var w=d[k]|b;if(m==0){Console.Write(BigInteger.Parse(Convert.ToString(w,2))/n);return;}d.Add(m,w);}}}

Затем, что касается вознаграждения: вознаграждение должно идти к aditsu, поскольку я думаю, что его алгоритм не может быть побежден с точки зрения производительности. Но самоответ Анатолия тоже удивителен.

Вот моя быстрая реализация в C #. Я полагаю, что в C ++ это может быть быстрее (возможно, в 2 раза). Скомпилировано и протестировано с Visual Studio 2010, .NET Framework 4, 64 бита, перенаправляя вывод в nul. Время: 00: 00: 05.2604315

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;
using System.Diagnostics;

class Program
{
   static BigInteger Find(int n)
   {
      var d = new Dictionary<int, long>();
      long kb;
      int km;
      d[n] = 0;
      for (kb = km = 1; ; kb *= 2, km = (km * 10) % n)
      {
         foreach (int key in d.Keys.Reverse())
         {
            int m = (km + key) % n;
            if (!d.ContainsKey(m))
            {
               long w = d[key] | kb;
               if (m == 0)
               {
                  return BigInteger.Parse(Convert.ToString(w, 2));
               }
               d.Add(m, w);
            }
         }
      }
   }

   static void Exec(int n, out string sq, out string sa)
   {
      var v = Find(n);
      sq = (v/n).ToString();
      sa = v.ToString();
   }  

   static void Main(string[] args)
   {
      // string n = Console.ReadLine();
      int limit = int.Parse(args[0]);
      string q ="", a = "";
      Stopwatch x = new Stopwatch();
      x.Start();
      for (int n = 1; n <= limit; n++)
      {
         Exec(n, out q, out a);
         Console.WriteLine("{0} {1} {2}", n, q, a);
      }
      x.Stop();
      Console.Error.WriteLine("{0}", x.Elapsed);
   }
}

C с GMP (621 байт, быстрый)

Я пытался быть быстрым и коротким, но предпочитал быстро. В этой реализации используется слегка улучшенная версия теоретико-числового ускорения, о котором я упоминал в комментарии к ответу aditsu .

Сохранить как pseudobinary.cи скомпилировать с gcc pseudobinary.c -lgmp -o pseudobinary. Обратите внимание, что это выделяет так много памяти для больших входов, что вам нужно будет скомпилировать ее для 64-битной платформы.

#include <gmp.h>
int main(int y,char*z[]){int i,n,b,c,e,f,m,*j,*k,*l,*r,*h;char *d,*s;mpz_t
B,I,Q;i=atoi(z[1]);n=i;for(b=0;n%10<1;++b)n/=10;for(;n%2<1;++b)n/=2;for(;n%5<1;++b)n/=5;if(n<2)--b;d=calloc(n,1);j=calloc(n,sizeof(int));r=calloc(99,sizeof(int));c=2;d[1]=1;*j=r[1]=e=1;l=j+1;for(s=0;!s;++c){r[c]=e=e*10%n;k=l;for(h=j;h<k;h++){f=*h;m=(e+f)%n;if(d[m]<1){*l++=m;if(m<1){s=malloc(99);memset(s,48,99);for(f=c;f;f=d[m=(m+n-r[f])%n])s[c-f]++;s[c]=0;h=k;}d[m]=c;}}}f=strlen(s);s[f]=48;s[f+b]=0;mpz_init_set_str(B,s,10);mpz_init_set_si(I,i);mpz_init(Q);mpz_divexact(Q,B,I);d=mpz_get_str(0,10,Q);printf("%s\n",d);return 0;}

Версия цикла для синхронизации (751 байт)

#include <gmp.h>
char **v;int main(){int i,n,b,c,e,f,m,*j,*k,*l,*r,*h;char *d,*s;mpz_t
B,I,Q;v=calloc(10001,sizeof(char*));v[1]=s=malloc(99);memset(s,48,99);*s=49;s[1]=0;for(i=0;++i<10001;){n=i;for(b=0;n%10<1;++b)n/=10;for(;n%2<1;++b)n/=2;for(;n%5<1;++b)n/=5;d=calloc(n,1);j=calloc(n,sizeof(int));r=calloc(99,sizeof(int));c=2;d[1]=1;*j=r[1]=e=1;l=j+1;for(;!v[n];++c){r[c]=e=e*10%n;k=l;for(h=j;h<k;h++){f=*h;m=(e+f)%n;if(d[m]<1){*l++=m;if(m<1){v[n]=s=malloc(99);memset(s,48,99);for(f=c;f;f=d[m=(m+n-r[f])%n])s[c-f]++;s[c]=0;h=k;}d[m]=c;}}}free(d);free(j);free(r);s=v[n];f=strlen(s);s[f]=48;s[f+b]=0;mpz_init_set_str(B,s,10);mpz_init_set_si(I,i);mpz_init(Q);mpz_divexact(Q,B,I);d=mpz_get_str(0,10,Q);printf("%s\n",d);free(d);s[f+b]=48;s[f]=0;}return 0;}

Версия без петель

#include <gmp.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

char **cache;

int main() {
    int i,n,shift,_kb,km,key,m,*ks,*ksi,*nksi,*res,*ii;
    char *d,*s;
    mpz_t B,I,Q;

    cache = calloc(10001,sizeof(char*));
    if (!cache) { printf("Failed to malloc cache\n"); return 1; }
    cache[1]=s = malloc(99);
    memset(s,48,99);
    *s=49;
    s[1]=0;
    for (i=0;++i<10001;) {
        n=i;
        for(shift=0;n%10<1;++shift)n/=10;
        for(;n%2<1;++shift)n/=2;
        for(;n%5<1;++shift)n/=5;

        d = calloc(n,1);
        if (!d) { printf("Failed to malloc d\n"); return 1; }

        ks = calloc(n,sizeof(int));
        if (!ks) { printf("Failed to malloc ks\n"); return 1; }

        res = calloc(99,sizeof(int));
        if (!res) { printf("Failed to malloc res\n"); return 1; }

        _kb = 2;
        d[1] = 1;
        *ks = res[1] = km = 1;
        nksi = ks + 1;

        for(;!cache[n];++_kb) {
            res[_kb] = km = km*10%n;
            ksi = nksi;
            for (ii = ks; ii < ksi; ii++) {
                key = *ii;
                m = (km + key) % n;
                if (d[m] < 1) {
                    *nksi++ = m;
                    if (m < 1) {
                        cache[n] = s = malloc(99);
                        if (!s) { printf("Failed to malloc s\n"); return 1; }
                        memset(s,48,99);
                        for(key=_kb;key;key = d[m = (m + n - res[key]) % n])s[_kb-key]++;
                        s[_kb]=0;
                        ii = ksi; // break
                    }
                    d[m] = _kb;
                }
            }
        }

        free(d);
        free(ks);
        free(res);

        // Add shift * '0'
        s=cache[n];
        key=strlen(s);
        s[key]=48;
        s[key+shift]=0;

        // convert to big integer, divide, print
        mpz_init_set_str(B,s,10);
        mpz_init_set_si(I,i);
        mpz_init(Q);
        mpz_divexact(Q,B,I);
        d = mpz_get_str(0,10,Q);
        if (!s) { printf("Failed to malloc quotient\n"); return 1; }
        printf("%s\n", d);
        free(d);

        // Remove shift * '0'
        s[key+shift]=48;
        s[key]=0;
    }
    return 0;
}

C + GMP, 669

Это действительно быстро для небольших чисел; он начинает задыхаться, когда результат имеет более 64 цифр.

#include<gmp.h>
#define B(x)(int)((x*(long)k)%n);
int*M,*H,P[99],n,x,p,q=2,e=1,k=10,y,f,z;char*E,C[99];int b(int k,int t){int
j=E[k],a=1<<(j-2);if(j<2){C[t]=49;return 1;}x=(int)((k+n-P[j]*(long)H[k]%n)%n);if(x)b(x,t);return a+b(H[k],t-a);}int
main(){scanf("%d",&n);E=calloc(n+1,1);M=calloc(n+1,4);H=malloc(n*4);M[1]=E[1%n]=P[1]=1;while(!E[0]){P[++e]=k;p=q;for(x=0;++x<p;){y=B(M[x])if(E[n-y]){E[0]=e;H[0]=M[x];break;}}if(!E[x=0])while(++x<p){y=B(M[x])for(z=0;z<p;++z){f=y+M[z];if(f>=n)f-=n;if(!E[f]){E[f]=e;H[f]=M[x];M[q++]=f;}}}k=B(k)}memset(C,48,98);C[99]=0;x=b(0,97);mpz_t
m,r;mpz_init(r);mpz_init_set_str(m,C+98-x,10);mpz_fdiv_q_ui(r,m,n);puts(mpz_get_str(C,10,r));}

Версия с циклом до 10000 (671 байт):

#include<gmp.h>
#define B(x)(int)((x*(long)k)%n);
#define N 10001
int M[N],H[N],P[99],n=0,x,p,q,e,k,y,f,z;char E[N],C[99];int b(int k,int t){int
j=E[k],a=1<<(j-2);if(j<2){C[t]=49;return 1;}x=(int)((k+n-P[j]*(long)H[k]%n)%n);if(x)b(x,t);return a+b(H[k],t-a);}int
main(){while(++n<N){memset(E,M[0]=0,n);M[1]=E[1%n]=P[1]=e=1;q=2;k=10;while(!E[0]){P[++e]=k;p=q;for(x=0;++x<p;){y=B(M[x])if(E[n-y]){E[0]=e;H[0]=M[x];break;}}if(!E[x=0])while(++x<p){y=B(M[x])for(z=0;z<p;++z){f=y+M[z];if(f>=n)f-=n;if(!E[f]){E[f]=e;H[f]=M[x];M[q++]=f;}}}k=B(k)}memset(C,48,98);C[99]=0;x=b(0,97);mpz_t
m,r;mpz_init(r);mpz_init_set_str(m,C+98-x,10);mpz_fdiv_q_ui(r,m,n);puts(mpz_get_str(C,10,r));}}

Вот несколько команд для тестирования моего кода, а также моих конкурентов и результатов на моем ноутбуке:

ls -l *.c*       
-rw-r--r-- 1 aditsu aditsu  669 Oct 27 15:01 mult-aditsu-single.c
-rw-r--r-- 1 aditsu aditsu  671 Oct 27 15:01 mult-aditsu.c
-rw-r--r-- 1 aditsu aditsu 3546 Oct 27 15:01 mult-anatoly.c
-rw-r--r-- 1 aditsu aditsu 6175 Oct 27 15:01 mult-anders.cpp
-rw-r--r-- 1 aditsu aditsu  621 Oct 27 15:01 mult-peter-single.c
-rw-r--r-- 1 aditsu aditsu  751 Oct 27 15:01 mult-peter.c

gcc -w -march=native -O3 mult-aditsu-single.c -lgmp -o mult-aditsu-single
gcc -w -march=native -O3 mult-aditsu.c -lgmp -o mult-aditsu
gcc -w -march=native -O3 mult-peter-single.c -lgmp -o mult-peter-single
gcc -w -march=native -O3 mult-peter.c -lgmp -o mult-peter
gcc -w -march=native -O3 --std=c99 mult-anatoly.c -o mult-anatoly
g++ --std=c++11 -march=native -O3 mult-anders.cpp -o mult-anders

for i in {1..5}; do time ./mult-anders mult-anders.txt; done
./mult-anders mult-anders.txt  0.34s user 0.00s system 99% cpu 0.344 total
./mult-anders mult-anders.txt  0.36s user 0.00s system 99% cpu 0.358 total
./mult-anders mult-anders.txt  0.34s user 0.00s system 99% cpu 0.346 total
./mult-anders mult-anders.txt  0.35s user 0.00s system 99% cpu 0.347 total
./mult-anders mult-anders.txt  0.34s user 0.00s system 99% cpu 0.344 total

for i in {1..5}; do ./mult-anatoly mult-anatoly.txt; done
Time: 0.254416
Time: 0.253555
Time: 0.245734
Time: 0.243129
Time: 0.243345

for i in {1..5}; do time ./mult-peter > mult-peter.txt; done
./mult-peter > mult-peter.txt  0.14s user 0.00s system 99% cpu 0.137 total
./mult-peter > mult-peter.txt  0.15s user 0.00s system 97% cpu 0.153 total
./mult-peter > mult-peter.txt  0.15s user 0.00s system 99% cpu 0.149 total
./mult-peter > mult-peter.txt  0.15s user 0.00s system 99% cpu 0.150 total
./mult-peter > mult-peter.txt  0.14s user 0.00s system 99% cpu 0.138 total

for i in {1..5}; do time ./mult-aditsu > mult-aditsu.txt; done
./mult-aditsu > mult-aditsu.txt  0.06s user 0.00s system 95% cpu 0.058 total
./mult-aditsu > mult-aditsu.txt  0.05s user 0.00s system 97% cpu 0.055 total
./mult-aditsu > mult-aditsu.txt  0.06s user 0.00s system 99% cpu 0.056 total
./mult-aditsu > mult-aditsu.txt  0.05s user 0.00s system 99% cpu 0.054 total
./mult-aditsu > mult-aditsu.txt  0.05s user 0.00s system 98% cpu 0.055 total

md5sum *.txt
6eef8511d3bc5769b5d9218be2e00028  mult-aditsu.txt
6eef8511d3bc5769b5d9218be2e00028  mult-anatoly.txt
6eef8511d3bc5769b5d9218be2e00028  mult-anders.txt
6eef8511d3bc5769b5d9218be2e00028  mult-peter.txt

T-SQL, 164 156 155 154 159 байт

(-1 байт. Спасибо Джонатан!)

(-1 больше, потому что почему у меня в конце есть пробелы? SMH)

(+5 понял, что мой гольф сломал вещи)

create function b(@ int)
returns int
as begin
declare @b varchar(max)='',@i int=@
while @>0SELECT @b=cast(@%2 as varchar)+@b,@/=2
return cast(@b as int)/@i
end

Я не знаю, почему я продолжаю возвращаться к этим вопросам, где я должен конвертировать в Binary ... T-SQL не знает, как это сделать правильно.

В любом случае, вот SQLFiddle .

Un-golfed:

create function binarySquare(@id int)
returns int 
as BEGIN

Насколько я знаю, большая часть этого материала требуется для написания функции на T-SQL.

    declare @bin nvarchar(max) = ''

Создайте пустую строку, которую мы будем хранить как наше двоичное число.

    declare @id2 int = @id

Сохраните входное значение для использования в конце. Кажется, должен быть способ использовать исходный ввод, даже если мы изменим значение, но я не могу его найти.

    while @id>0
      BEGIN
        SET @bin = cast(@id%2 as varchar(1)) + @bin

Итак, мы берем наш исходный ввод, изменим его на 2, чтобы найти остаток, и это будет наша следующая маленькая цифра. Например, 5% 2 = 1

        SET @id = @id/2

Затем мы берем наш номер и делим его пополам. Поскольку это intтип, он округляет его до ближайшего целого числа, поэтому 5/2 = 2. КОНЕЦ Затем мы перебираем это до тех пор, пока значение не станет 0. Таким образом, мы в итоге получим 5% 2 = 1 5/2 = 2 2 % 2 = 0 2/2 = 1 1% 2 = 1 1/2 = 0, что дает нам значение нашей двоичной строки 101.

    declare @binNum int = (SELECT cast(@bin as int))

Мы берем нашу двоичную строку и снова конвертируем ее в int.

    return @binNum/@id2

Мы возвращаем нашу двоичную строку, intделенную на наше исходное значение, в соответствии с источником вопроса.

END

Рубин, 46 байт

Я действительно должен исключить цикл while с помощью альтернативного цикла.

n,k=gets,0;$_="#{n.to_i*k+=1}"while/[^01]/;p k

Редактировать: Спасибо @manatwork за сбрить 1 байт!

Edit2: Спасибо @histocraft за безумные 9 байтов!

Редактировать: Спасибо @manatwork еще раз за сбрить 7 байтов!

Скала, 114 байт

val i=scala.io.StdIn.readInt;Stream.from(1).foreach{x=>if((i*x+"").map{_.asDigit}.max<2){print(x);System.exit(0)}}

Читаемая версия

val i=scala.io.StdIn.readInt
Stream.from(1).foreach{x => 
    if((i*x+"").map{_.asDigit}.max<2) {
        print(x)
        System.exit(0)
    }
}

gawk4 перебор, 28 + 2 = 30 байт

{while(++n*$0~/[2-9]/);}$0=n

Должен быть вызван с -M возможностью использования больших чисел. Конечно, это смехотворно медленно, использование больших чисел замедляет его еще больше, но теоретически вход не ограничен, а использование ОЗУ незначительно.

Пример использования (если у вас есть время впустую ;))

echo 27 | awk -M '{while(++n*$0~/[2-9]/);}$0=n'

gawk4 оптимизирован, 69 + 2 = 71 байт

{for(;!a[0];NR*=10)for(i in a)a[j=(s=a[i]+NR)%$0]?0:a[j]=s}$0=a[0]/$0

Ну, это закончилось тем, что стало клоном ответа Адицу. Посмотрев на этот вопрос, я все еще выяснял, как закодировать часть суммы подмножества, когда я не мог удержаться, глядя на другие ответы здесь.

В массиве awk элементы имеют (странное?) Поведение, которое заключается в том, что если вы сравниваете несуществующий элемент с чем-то, он каким-то образом инициализируется как пустой перед сравнением (я признаю, что не совсем уверен в том, что там происходит). Таким образом , после проверки !a[0]на for(i in a)цикл начинается даже без инициализации a[$0]для0 как и aditsu.

Конечно, -Mопция должна быть использована и для этого.

Хотя он довольно быстрый, он все же заметно медленнее, чем Python. На 79992это уходит 2 секунды на моем 2GHz Core2Duo. И я бы не сказал, что он работает для входов до 2 ^ 31, потому что в худшем случае он должен создать массив больших чисел (для этого gawk4 использует GMP), который имеет размер входного числа. В качестве «бонуса» большие массивы очень-очень медленно работают в awk ...

Дьялог АПЛ , 25

Это определяет правильную программу «P» (не просто безымянную функцию):

P←2∘{0::⍵∇⍨1+⍺⋄⍺⊣~⍎¨⍕⍺×⍵}

2∘начинайте с 2 в качестве левого аргумента,
0::если есть какая-либо ошибка ...
⍵∇⍨1+⍺вызывайте себя с увеличенным левым аргументом,
⍺×⍵умножайте левый и правый аргументы,
⍕превращая их в строку,
⍎¨превращайте каждый символ в
~попытку числового логического НЕ (в случае неудачи перейдите к обработке ошибок выше, еще ...)
⍺⊣вернуть текущий левый аргумент.

      P 2
50
      P 21
481
      P¨⍳8    ⍝ 1 through 8
10 5 37 25 2 185 143 125