Ir para o conteúdo

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