Concatenar Números

Dado um número inteiro positivo N, concatenar esse número com ele próprio uma ou mais vezes de modo que o número resultante seja divisivel por um número inteiro positivo k.

Soluções que envolvam o uso de números de ordens de grandeza maiores que os dados iniciais em geral são ineficientes e resultam em esgotamento dos recursos computacionais disponíveis pelo que não são válidas.

Alguns exemplos

Exemplos de input/output:

Input: 2 9
Output: 9
Explicação: o resto da divisão de 222.222.222 por 9 é 0.
Processo: N = 2 e k = 9

1. 2 não é divisivel por 9
2. 22 não é divisivel por 9
3. 222 não é divisivel por 9
4. 2222 não é divisivel por 9
5. 22222 não é divisivel por 9
6. 222222 não é divisivel por 9
7. 2222222 não é divisivel por 9
8. 22222222 não é divisivel por 9
9. 222222222 é divisivel por 9!

Input: 121 11
Output: 1
Explicação: 121 é divisivel por 11.

Input: 1 2
Output: -1
Explicação: Não conseguimos formar um número par só com 1's.

Input: 35 98765
Output: 9876
Nota: O número resultante tem 9876 * 2 digitos.

Input: 1000000000 3
Output: 3
Explicação: 100000000010000000001000000000 é divisivel por 3.

Exemplos de implementações da solução

C++

#include <iostream>
#include <cstring>
using namespace std;

char restos[100002];

int getSmallest(int n, int k) { 
    memset( restos , 0 , sizeof(restos) );
    long long y = 1 , a = n % k;
    while (y<=n) 
        y*=10;      // calcular a pontencia de 10 necessaria
    int resp;
    for ( resp = 1 ; resp <= k ; resp++ ) {
        if ( a == 0 )       return resp;
        if ( restos[a] )    return -1;
        restos[a] = 1;
        a = ( (a*y)+n ) % k;
    }
    return -1;
}

int main()
{
    int N , K;
    while (cin >> N >> K) {     
        cout << getSmallest(N,K) << endl;
    }
    return 0;
}

Solução por mogers.

Perl

use POSIX qw(ceil log10);

$c  = $ARGV[0];
$d  = $ARGV[1];

#inserir os numeros manualmente aqui caso necessario
#$c = 200;
#$d = 15;

$factor = 10**(ceil(log10($c)));

$rest   = $c % $d;
$rest_p = $rest;

my %rests;
$success = 1;
for($i = 1; $rest!=0; $i++){
    $rest_p = ($rest_p * $factor) % $d;
    $rest   = ($rest_p + $rest) % $d;

    if ($rests{$rest} == 1){
        $success = 0;
        last;       
    }   
    $rests{$rest} = 1;
}


if ($success == 0){
    print "Problema sem solcucao, impossivel encontrar um numero divisivel por $d concatenando $c\n";
}
else{
    foreach (1 .. $i) {
        print $c;
    }
    print " e divisivel por $d\n";
}

Solução por pedrotuga.