3で終わる数字は、すべて1を持つ複数の倍数を持っています

Question

こんにちは、ここではAdobeインタビューで質問されたQです。

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. 

あなたが効率的なソリューションで

Answer 1

を私に提供することはできますが、今答えを得た:)ここ

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

Answer 2

は1、11、111、111をしようとしていることをより効率的にそれを行うための試みであります..これは報われるだろうか？一度に数字を1つ試すよりも、よりエレガントな答えがありますか？

1、11、111、...を（10^k - 1）/ 9と書くと、除算は正確であることが分かります。 10x + 3という形式のターゲット番号が与えられたとき、最小のk（10^k - 1）/ 9 = Y（10x + 3）を求めたい。ここでYは整数である。 10^k = 1 mod 9（10x + 3）の小さな解を探します。算術モジュ9（10x + 3）が必ずしもグループを形成するわけではないことを除いて、これはhttp://en.wikipedia.org/wiki/Discrete_logarithmですが、http://en.wikipedia.org/wiki/Baby-step_giant-stepアルゴリズムが適用され、kの値を一度に1つずつ検索するのではなく、 。出力サイズとは無関係に

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

ソリューション：

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 */ 

}