Na stronie Code Review natrafiłem na pytanie, które wydaje się interesujące. Myślę, że OP robi to źle, ale nie mogę być pewien ... Więc rozwiążmy to dla niego! (napisz program, a nie funkcję / procedurę)

Dane wejściowe (standardowe lub podobne):

Liczba całkowita xw notacji dziesiętnej. Jest większy niż 1 i mniejszy niż 2 ^ 31.

Wyjście (standardowe lub podobne):

Liczba całkowita yw notacji dziesiętnej. Produkt x * yw postaci dziesiętnej musi zawierać tylko cyfry 0 i 1. Musi to być minimalna liczba większa niż 0.

Uwaga: wyjście nie jest ograniczone - jeśli minimum ywynosi około 10 ^ 100, twój program musi wypisać wszystkie swoje 100 cyfr (nie wiem, czy istnieje rozsądny limit, na przykład 2 ^ 64, włączony) y- nie rozwiązał go ).

Twój program powinien zakończyć się w rozsądnym czasie (1 sekunda? 1 godzina? - coś takiego) dla wszystkich xw zasięgu.

Premia:

Jeśli twój program nie ma ograniczenia wielkości danych wejściowych (oprócz RAM) i ma złożoność wielomianową, pomnóż liczbę bajtów programu przez 0.8i zaokrąglaj w dół.

Przykład: wejście 2; wyjście 5, ponieważ 2 * 5 = 10

Przykład: wejście 21; wyjście 481, ponieważ 21 * 481 = 10101

Oświadczenie: Nie jestem odpowiedzialny za pytanie w witrynie Code Review. W przypadku jakichkolwiek rozbieżności jedynie powyższy opis należy traktować jako właściwą specyfikację.

OEIS A079339

Pyth, 9 bajtów

f!-`*TQ10

Demonstracja

Dla każdej wielokrotności przekonwertuj na ciąg, odejmij cyfry w 10(używając w tym przypadku przydatnej int Pyth'a do str stringu), a następnie logicznie zaneguj wynik, kończąc wyszukiwanie tylko wtedy, gdy zostanie znaleziona poprawna wielokrotność.

Rozwiązanie premiowe, 10 bajtów:

f.xi`*TQ2Z

To rozwiązanie faktycznie sprawdza, czy ciąg znaków reprezentujący liczbę może być traktowany jako liczba binarna ( i ... 2) i kończy się, gdy błąd nie zostanie zgłoszony podczas tej próby.

Python 2, wydajne rozwiązanie, 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

Dzięki Sp3000 za kilka wskazówek golfowych.

Wzywam wszystkich innych do opublikowania (we własnych odpowiedziach), ile czasu zajmuje uzyskanie wyniku do wprowadzenia 72lub 99:) Jeśli są one naprawdę szybkie, spróbuj czegoś podobnego 79992(nadal <1 s tutaj).

Wyjaśnienie:

Myślałem, że to nie jest konieczne (ponieważ kod jest dość czytelny), ale dostałem prośbę, więc oto:

Pierwszym pomysłem jest to, że liczba wyglądająca na binarną jest sumą 1 lub więcej różnych potęg równych 10. Dlatego możemy próbować dodawać różne potęgi 10 na różne sposoby, aż otrzymamy resztę 0.

Jeśli robimy to naiwnie, to to samo, co generowanie wszystkich liczb binarnych i testowanie ich. Ale wiele resztek pozostanie takich samych. Lepszym sposobem jest zapisanie tylko najmniejszej liczby, która dała pewną pozostałą część, i sukcesywne dodawanie większych mocy 10 do liczb, które zanotowaliśmy. Tak właśnie działa program.

djest słownikiem / mapą, w której klucze są resztkami, a wartości są liczbami binarnymi z resztą. Inicjał n:0jest szczególnym przypadkiem: ma to być 0:0, abyśmy mogli zacząć dodawać do niego moce, ale algorytm zatrzymuje się po znalezieniu klucza 0, więc użyłem nzamiast tego, co gwarantuje, że będzie miało ten sam efekt i nie będzie kolidować z innymi wartościami.

Następnie zaczynamy dodawać moce 10 (zapisane w k) do wszystkich istniejących liczb i rejestrować pozostałe. Dodajemy kdo reszty: (x+k)%ni do liczby: d[x]+ki zapisujemy ją tylko wtedy, gdy jest to nowa reszta:, d.setdefault(…)następnie przejdź do następnej potęgi: k*=10i powtarzaj, aż otrzymamy klucz 0:while min(d)

Na koniec d[0]podaje binarnie wyglądającą liczbę, która pozostała 0 mod n, więc dzielimy ją, naby uzyskać rozwiązanie.

Uwaga: program można usprawnić, unikając dużych liczb (rejestrowanie wykładników zamiast potęg 10 i obliczanie reszt potęg z poprzednich wartości), ale to kod golfowy, więc ...

W rzeczywistości tutaj napisałem szybszą wersję:

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 bajtów

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

Śledzi numer wejściowy ni bieżącą wielokrotność a. Kiedy awygląda jak binarny, wypisz stosunek a/n. Aby sprawdzić, czy liczba składa się z 0„i 1”, porównujemy maksymalny znak w reprezentacji ciągu z '1'.

Używa str(a)zamiast `a`unikać długich zakończeń L. Niestety 'L'jest większy niż '1'.

Perl, 27 bajtów

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

Licząc shebang jako jeden, dane wejściowe są pobierane ze standardowego wejścia.

Przykładowe użycie

$ echo 2 | perl dec-bin.pl
5

$ echo 21 | perl dec-bin.pl
481

$ echo 98 | perl dec-bin.pl
112245

Perl, 25 bajtów

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

Poprawę dwa bajt przez @skmrx .

Zamiast sprawdzać pod kątem wyrażenia regularnego, próbuje to ocenić produkt jako literał binarny. Po awarii przechodzi do następnego. Zazwyczaj octfunkcja ta byłaby używana do tego celu, ale po cichu przycina nieprawidłowe cyfry, co nie jest przydatne w tym wyzwaniu.

Perl, 40 bajtów

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

O wiele bardziej wydajne rozwiązanie. Iterujemy reprezentacje binarne, interpretujemy je jako podstawę 10, a następnie sprawdzamy podzielność. Czas działania dla wszystkich wartości poniżej 100 jest nieistotny.

Przykładowe użycie

$ echo 72|perl dec-bin.pl
1543209875

$ echo 99|perl dec-bin.pl
1122334455667789

JavaScript, 43 bajty

To skończyło się znacznie krócej, niż myślałem. Zasadniczo zwiększa ysię o 1 do y * (input number) = (binary-looking number). Oczywiście dość nieefektywne.

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

JavaScript (bardziej wydajne rozwiązanie), 53 bajty

Ten zwiększa się yw postaci binarnej do y / (input number) = (number without a remainder). Potem wyprowadza (number without a remainder).

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

JavaScript (jeszcze bardziej wydajne rozwiązanie), 76 bajtów

Ten łączy obie poprzednie metody opisane powyżej. Sprawdza przyrosty ydo momentu, aż albo y * (input number) = (binary-looking number)(co oznacza, że ​​dane wyjściowe są y) LUB y / (input number) = (number without a remainder)(co oznacza, że ​​dane wyjściowe są (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 bajtów

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

Edycja: @Jan Dvorak pomógł mi zaoszczędzić 4 bajty.

Edycja: @BlackCap zapisał 2 bajty, przechodząc do donotacji. Dzięki!

Python 2, 67 65 63 60 bajtów

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

Dzięki Status za 2 bajty i Shebang na 5 bajtów!

JavaScript (ES6) 222 250

Korzystanie z matematyki o dowolnej precyzji (operowanie na ciągach cyfr dziesiętnych)

Można to trochę pograć w golfa (gotowe), ale podoba mi się to, że nie ogranicza się to do standardowych liczb JS (17 cyfr dziesiętnych precyzji) i jest szybki.

Przetestuj poniższy fragment kodu w przeglądarce zgodnej z EcmaScript 6. Czas jest dopuszczalny do 9998 - nie próbuj 9999 i bądź cierpliwy z 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>

Bardziej czytelny

Jest to pierwsza wersja z modułem i długim podziałem jako oddzielnymi funkcjami.

// 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 bajtów

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

Pyth, 10 bajtów

f<eS`*TQ`2

Uruchom kod.

Port mojego Pythona odpowiedź , biorąc od Maltysen zastosowanie fdo znalezienia pierwszego dodatnią liczbę, która spełnia warunek.

PHP, 50 bajtów

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

Niektóre przypadki testowe

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

CJam, 19 17 16 bajtów

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

Wypróbuj online

Rozwiązanie z użyciem siły brutalnej, próbując wartości kolejno, aż do znalezienia jednego spełniającego warunek.

Najnowsza wersja oszczędza 2 bajty dzięki użyciu Aszamiast "01"budowania łańcucha zawierającego 0i 1, jak sugeruje @aditsu. Całkowicie zaproponowane rozwiązanie w komentarzu oszczędza kolejny bajt, ale wygląda całkiem inaczej niż mój, więc nie chciałem umieszczać go pod własnym nazwiskiem.

I jeszcze 1 bajt zapisany przez @Dennis.

Wyjaśnienie:

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 bajtów

-25 bajtów dzięki @aditsu

prawie tak wydajne jak rozwiązanie @ 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

Zamiast próbować przechodzić między mnożnikami w porządku rosnącym, próbuję zapętlać produkty, które generuję w formie „binarnej”.

Java, 213 bajtów

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);}}

Wykorzystuje BigIntegers i jako taki ma (dla wszystkich uzasadnionych intencji i celów) nieograniczony rozmiar danych wejściowych. Nie jestem jednak pewien, czy złożoność zależy od tempa wzrostu naszej funkcji tutaj.

Dzięki geobitom i ypnypn za oszczędność garści bajtów.

C, 3675 bajtów

Tak długo na 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);
    }
}

Uruchomić bez parametrów wiersza poleceń - to dostaje nod stdini wysyła wynik stdout. Uruchom z nazwą pliku - zapisuje wyniki dla n = 1...10000tego pliku i mierzy czas.

Wydajność dla 1 ... 10000: 140 ms

Ten kod wykorzystuje algorytm zaproponowany przez aditsu , zaimplementowany w C dla prędkości. Nie próbowałem go golfa, więc kod będzie łatwiejszy do odczytania.

Najpierw zaimplementowałem go w C ++, std::maprejestrując wyniki wyszukiwania, i było to dość powolne. Jednak klucze mapsą kolejnymi liczbami całkowitymi (nazywam je mods, ponieważ reprezentują liczby modulo n), więc naturalne jest użycie tablicy - więc przepisałem ją w C.

Dodatkowa optymalizacja dotyczy wartości mapowania - aby uniknąć zapisania dużej liczby całkowitej dla każdej mod, przechowuję tam tylko największą potęgę 10 - wystarczy tyle informacji, aby przejść do poprzedniego mod. Tak więc tablica jest naprawdę drzewem / wykresem wyszukiwania. Kiedy wyszukiwanie dotrze do mod = 0, śledzenie węzłów drzewa z powrotem do katalogu głównego daje moc 10 w kolejności malejącej.

Ponieważ wyszukiwanie zwykle zatrzymuje się dość szybko, a odwiedzana jest tylko niewielka część węzłów, potrzebuję listy aktywnych węzłów. Jest zaimplementowany jako tablica mod_listo długości mod_list_length.

Niektóre statystyki środowiska wykonawczego (na komputerze z 16 GB pamięci RAM, co wydaje się być ważne dla dużych n, ponieważ program przydziela 5nbajty pamięci):

• Wejście 99999999- 2 sekundy
• Wejście 999999999- 27 sekund (wynikiem jest 111111111222222222333333333444444444555555555666666666777777777888888889- prawdopodobnie największy możliwy wynik dla 32-bitowych liczb całkowitych)
• Wejście 2147483647- 26 sekund (wynik jest 4661316525084584315813)
• Wejście 1999999998- 52 sekundy (prawdopodobnie najdłuższy możliwy czas działania dla 32-bitowych liczb całkowitych)

C ++ 11, wiele bajtów, bardzo szybko, wow (1,5 s dla 1999999998, 0,2 s dla 1… 10000)

(Gra w golfa w wersji Python poniżej.)

Zaczynamy od koncepcji nieco podobnej do rozwiązania aditsu, w której indukcyjnie budujemy kolekcję modułowych resztek, które są osiągalne w n krokach. Ale zamiast czekać, aż znajdziemy resztę 0, sprawdzamy dwie znalezione resztki aib tak, że a · 10 ^ n + b = 0. To podejście w środku spotkania zmniejsza o połowę głębokość drzewa wyszukiwania, więc jest to znacznie szybciej na dużych wejściach i zużywa znacznie mniej pamięci.

Niektóre punkty odniesienia:

$ 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

Kod:

#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 bajtów (8,6 sekundy w 1999999998 z 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()

Matematyka 115 bajtów

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 bajtów

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);}}

Ogromne podziękowania dla aditsu :)

Pyth - 12 11 bajtów

Używa filtra z argumentem numerycznym, aby uzyskać pierwszą liczbę naturalną, która spełnia predykat, domyślnie jest to 1, czego chcemy. Ustaw inaczej, aby sprawdzić, czy tylko zera i jedynki.

f!-j*QT10U2

Pakiet testowy .

R, 45 bajtów

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

Stosowanie:

> 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

Java, 198 193 181 bajtów

Dzięki @aditsu za zgolenie 5 bajtów ORAZ zwiększenie zakresu liczb testowalnych!

Zauważ, że niektóre wartości zapętlają się ujemnie z powodu tego, jak Java analizuje liczby całkowite. Można to obejść przez BigInteger, ale premia była po prostu mniej cenna.

Wiem, że nie zamierzam wygrywać, ale mam nadzieję, że inspiruje to inne, krótsze odpowiedzi.

klasa 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) {}}}}

Niegofolowany:

klasa A {
   public static void main (String [] a) {
      for (long i = 1 ;; i ++) {// nieskończona pętla zaczynająca się od 1
         spróbuj {// jeśli wystąpi błąd podczas próby przetworzenia pliku binarnego, uruchom ponownie, dodając 1 do i
            long b = Long.parseLong (a [0]); // Na później - deklaracja była krótsza niż dwukrotne użycie
            jeśli (b * i <0) pęknie; // Wyjdź z programu, jeśli mamy zapętlony.
            Long.parseLong (b * i + "", 2); // Pomnóż i sprawdź, czy jest to wartość binarna, w przeciwnym razie wyrzuć błąd i wróć na górę pętli
            System.out.println (b); // Wydrukuj to
         } catch (wyjątek e) {} // nic nie rób w catch
      }
   }
}

C, 107 101 bajtów ( 105 99 bajtów dla 32 bitów)

Istnieje wyraźny brak odpowiedzi w C na temat golfa kodowego. Rzeczywiście, C nie jest najlepszym wyborem do pisania najmniejszego możliwego programu, ale nie jest tak źle:

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);}

Możesz obejść się bez #include, ale wtedy wszystkie definicje funkcji będą niejawne. Główną wadą jest to, że powoduje to założenie, że wszystkie funkcje zwracają wartości int. Jest to problem na maszynach 64-bitowych dla funkcji, które faktycznie zwracają wskaźnik. Jeśli korzystasz z komputera 32-bitowego, powyższe rozwiązanie można ogolić 2 bajty:

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

Nieco bardziej czytelna wersja:

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);
}

Czas C # w pobliżu 5 sekund (od 1 do 10000)

Zgodnie z życzeniem, oto program C # w golfa odpowiadający na oryginalne wyzwanie. Wprowadź jako argument wiersza poleceń, wyślij do konsoli.

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);}}}

Jeśli chodzi o nagrodę: nagrodę należy przejść do aditsu, ponieważ uważam, że jego algorytmu nie da się pokonać pod względem wydajności. Ale anatoligia samo odpowiedź jest również niesamowita.

Oto moja szybka implementacja w C #. Podejrzewam, że w C ++ może być szybszy (może 2x). Skompilowane i przetestowane z Visual Studio 2010, .NET Framework 4, 64 bity, przekierowując dane wyjściowe do nul. Czas: 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 z GMP (621 bajtów, szybki)

Starałem się być szybki i niski, ale szybko faworyzowałem. Ta implementacja wykorzystuje nieco ulepszoną wersję teoretycznego przyspieszenia, o którym wspomniałem w komentarzu do odpowiedzi aditsu .

Zapisz jako pseudobinary.ci kompiluj z gcc pseudobinary.c -lgmp -o pseudobinary. Zauważ, że przydziela to tyle pamięci dla dużych danych wejściowych, że będziesz musiał ją skompilować dla platformy 64-bitowej.

#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;}

Wersja pętli dla taktowania (751 bajtów)

#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;}

Wersja bez golfa

#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

Jest to bardzo szybkie w przypadku małych liczb; zaczyna dusić się, gdy wynik ma więcej niż 64 cyfry.

#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));}

Wersja z zapętleniem do 10000 (671 bajtów):

#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));}}

Oto kilka poleceń do testowania mojego kodu, a także moich konkurentów i wyników na moim laptopie:

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 bajtów

(-1 bajt. Dzięki Jonathan!)

(-1 więcej, bo dlaczego mam spacje końcowe na liniach? SMH)

(+5 zdałem sobie sprawę, że moje golfa zepsuły się)

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

Nie wiem, dlaczego ciągle wracam do tych pytań, w których powinienem przekonwertować na Binary ... T-SQL nie wie, jak to zrobić poprawnie.

W każdym razie oto SQLFiddle .

Bez golfa:

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

O ile mi wiadomo, większość tych rzeczy jest wymagana do napisania funkcji w języku T-SQL.

    declare @bin nvarchar(max) = ''

Utwórz pusty ciąg, który będziemy przechowywać jako nasz numer binarny.

    declare @id2 int = @id

Zapisz wartość wejściową do wykorzystania na końcu. Wydaje się, że powinien istnieć sposób na użycie oryginalnego wejścia, nawet jeśli zmienimy wartość, ale nie mogę jej znaleźć.

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

Więc bierzemy nasze oryginalne wejście, MOD to z 2, aby znaleźć resztę, a to będzie nasza następna najmniejsza cyfra. Na przykład 5% 2 = 1

        SET @id = @id/2

Następnie bierzemy nasz numer i dzielimy go na pół. Ponieważ jest to inttyp, zaokrągla go w dół do najbliższej liczby całkowitej, więc 5/2 = 2. KONIEC Następnie przechodzimy przez to, aż wartość wynosi 0. Tak więc otrzymujemy 5% 2 = 1 5/2 = 2 2 % 2 = 0 2/2 = 1 1% 2 = 1 1/2 = 0, co daje nam wartość ciągu binarnego 101.

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

Bierzemy nasz ciąg binarny i ponownie konwertujemy go na inny int.

    return @binNum/@id2

Zwracamy ciąg binarny intpodzielony przez naszą pierwotną wartość, według źródła pytania.

END

Rubinowy, 46 bajtów

Naprawdę powinienem wyeliminować pętlę while za pomocą alternatywnej pętli.

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

Edycja: Dzięki @manatwork za zgolenie 1 bajta!

Edit2: Dzięki @histocraft za szalone 9 bajtów!

Edycja: Jeszcze raz dziękuję @manatwork za golenie 7 bajtów!

Scala, 114 bajtów

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

Wersja do odczytu

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

brutalna siła gawk4, 28 + 2 = 30 bajtów

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

Musi zostać wywołany za pomocą -M opcją używania dużych liczb. Oczywiście jest to absurdalnie wolne, użycie dużych liczb spowalnia go jeszcze bardziej, ale teoretycznie wejście nie jest ograniczone, a użycie pamięci RAM jest znikome.

Przykład użycia (jeśli masz czas do stracenia ;))

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

Zoptymalizowany gawk4, 69 + 2 = 71 bajtów

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

Cóż, ostatecznie okazało się, że jest to klon odpowiedzi aditsu. Po spojrzeniu na to pytanie wciąż zastanawiałem się, jak zakodować część sumy częściowej, kiedy nie mogłem się oprzeć spojrzeniu na inne odpowiedzi tutaj.

W tablicy awk elementy mają takie (dziwne?) Zachowanie, że jeśli porównasz nieistniejący element z czymś, zostanie on w jakiś sposób zainicjowany jako pusty przed porównaniem (przyznam, że nie jestem całkiem pewien, co się tam dzieje). Więc po sprawdzeniu !a[0]przez for(i in a)starty pętli nawet bez inicjowania a[$0]aby 0jak aditsu zrobił.

Oczywiście w tym -Mcelu należy również skorzystać z opcji.

Chociaż jest dość szybki, wciąż jest znacznie wolniejszy niż Python. Do 79992tego zajmuje około 14 sekund na moim Core2Duo 2GHz. I nie powiedziałbym, że działa dla danych wejściowych do 2 ^ 31, ponieważ w najgorszym przypadku musi zbudować tablicę dużych liczb (gawk4 używa do tego GMP), która ma wielkość liczby wejściowej. Jako „bonus” duże tablice są bardzo wolne w awk ...

Dyalog APL , 25

Definiuje to odpowiedni program „P” (nie tylko funkcję bez nazwy):

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

2∘zacznij od 2 jako lewy argument,
0::jeśli wystąpi błąd ...
⍵∇⍨1+⍺wywołaj się z przyrostowym lewym argumentem
⍺×⍵pomnóż lewy i prawy argument
⍕przekształć w łańcuch,
⍎¨aby każdy znak stał się
~logiczną próbą NIE (jeśli się nie powiedzie, przejdź do obsługi błędów powyżej, w przeciwnym razie ...)
⍺⊣zwraca bieżący lewy argument.

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