Numery kończące się na 3 mają co najmniej jedną wielokrotność z wszystkimi

Question

Witam Oto Q, która została zadana w Adobe Interview.

Numbers ending in 3 have at least one multiple having all ones. 
for eg., 3 and 13 have amultiples like 111 and 111111 respectively. Given such 
a no. , find the smallest such multiple of that number. The multiple can 
exceed the range of int, long. You cannot use any complex data structure. 

Czy możesz podać mi skutecznego rozwiązania

Answer 1

dostałem odpowiedź teraz :)

int count=1, rem=1; 
while(rem) 
{ 
rem= (rem*10+1)%n; count++; 
} 
while(count--){ cout<<"1";} 

Answer 2

Oto próba zrobić wydajniej, które starają 1, 11, 111, 111 ... Czy to się opłaca. Czy bardziej elegancka odpowiedź jest lepsza od próbowania liczb po jednym na raz?

Napisz liczby 1, 11, 111, ... (10^k - 1)/9, gdzie podział jest znany jako dokładny. Biorąc pod uwagę liczbę docelową w postaci 10x + 3, chcemy znaleźć najmniejsze k rozwiązania (10^k - 1)/9 = Y (10x + 3), gdzie Y jest liczbą całkowitą. Szukaj małych rozwiązań 10^k = 1 mod 9 (10x + 3). Jest to http://en.wikipedia.org/wiki/Discrete_logarithm, z tym że arytmetyczny mod 9 (10x + 3) niekoniecznie tworzy grupę - jednak algorytm http://en.wikipedia.org/wiki/Baby-step_giant-step powinien nadal obowiązywać i może być używany do wyszukiwania stale rosnących zakresów k, zamiast przeszukiwania możliwych wartości k po jednym naraz .

Answer 3

#include <iostream> 
using namespace std; 

int main() { 
    int t; 
    cin>>t; 
    while(t--){ 
     long long n; 
     cin>>n; 
     long long cur = 1; 
     while(cur%n!=0){ 
      cur = cur*10+1; 
     } 
     cout<<cur<<endl; 
    } 
    return 0; 
} 

Answer 4

Rozwiązanie niezależne od wielkości wyjściowej:

public String ones(int n) 
{ 
    int i, m = 1; 
    String num="1"; 

    for (i = 1; i <= n; i++) { 
       if (m == 0) 
       return num; 
      /* Solution found */ 
      num=num+"1"; 
      m = (10*m + 1) % n; 
    } 
    return null; /* No solution */ 

}