Divisibilidad de unidades repetidas

Un número que consiste en un número completamente repetido de veces uno se dice que es Unidad Repetida. Definiremos R(k) de longitud k número de unidad repetido. Por ejemplo, R(6) = 111111. 
Para un número dado n, un entero positivo y MCD(n, 10) = 1, existe un valor k tal que R(k) es divisible por n. Ahora sea A(n) el menor valor de k, es decir, A(n) = k. 
Por lo tanto, tenemos que encontrar para el valor dado de n el menor valor de A(n) para el cual k veces repetidas uno se divide por n.
Ejemplos: 
 

Input : n = 7
Output : A(7) = 6
A(7) = 6 means 6 times one i.e. (111111) is divided by 7.

Input : n = 41
Output : A(41) = 5
A(41) = 5 means 5 times one i.e. (11111) is divided by 41.

En primer lugar, si el número dado debe ser coprimo con 10; de lo contrario, devuelva 0. 
Si el número dado es coprimo con 10, entonces tenemos que encontrar el número más pequeño k tal que R(k) = 0 mod n . 
Considere las unidades repetidas R(1), R(2), R(3), R(4) y así sucesivamente. Para cada unidad repetida R(j) suponga que al calcular el resto de R(j) dividido por n. Hay n residuos concebibles. Obtenemos que R(i), R(j) donde i < j tienen el mismo resto cuando se divide por n. De ello se deduce que R(j) – R(i) se divide por n. Esta diferencia se repite unidad multiplicada por potencia de 10. Pero, como sabemos que 10 y n son primos relativos, n divide a R(k).
 

// CPP program to find least value of
// k for which R(k) is divisible by n
#include <bits/stdc++.h>
using namespace std;
 
// To find least value of k
int repUnitValue(int n)
{
 
    // To check n is coprime or not
    if (n % 2 == 0 || n % 5 == 0)
        return 0;
 
    // to store R(k) mod n and 10^k
    // mod n value
    int rem = 1;
    int power = 1;
    int k = 1;
    while (rem % n != 0)
    {
        k++;
        power = power * 10 % n;
        rem = (rem + power) % n;
    }
     
    return k;
}
 
// Driver code
int main()
{
    int n = 13;
    cout << repUnitValue(n);
    return 0;
}

// Java program to find least value of
// k for which R(k) is divisible by n
import java.util.*;
 
class GFG {
 
    // To find least value of k
    public static int repUnitValue(int n)
    {
         
        // To check n is coprime or not
        if (n % 2 == 0 || n % 5 == 0)
            return 0;
 
        // to store the R(k) mod n and
        // 10^k mod n value
        int rem = 1;
        int power = 1;
        int k = 1;
        while (rem % n != 0)
        {
            k++;
            power = power * 10 % n;
            rem = (rem + power) % n;
        }
         
        return k;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int n = 13;
        System.out.println(repUnitValue(n));
    }
}

# python program to find least value of
# k for which R(k) is divisible by n
 
# To find least value of k
def repUnitValue(n):
     
    # To check n is coprime or not
    if (n % 2 == 0 or n % 5 == 0):
        return 0
 
    # to store R(k) mod n and 10^k
    # mod n value
    rem = 1
    power = 1
    k = 1
    while (rem % n != 0):
         
        k += 1
        power = power * 10 % n
        rem = (rem + power) % n
     
    return k
     
# Driver code
n = 13
print(repUnitValue(n))
 
# This code is contributed by Sam007.

// C# program to find least value of
// k for which R(k) is divisible by n
using System;
 
public class GFG {
     
    // To find least value of k
    public static int repUnitValue(int n)
    {
         
        // To check n is coprime or not
        if (n % 2 == 0 || n % 5 == 0)
            return 0;
 
        // to store the R(k) mod n and
        // 10^k mod n value
        int rem = 1;
        int power = 1;
        int k = 1;
        while (rem % n != 0)
        {
            k++;
            power = power * 10 % n;
            rem = (rem + power) % n;
        }
         
        return k;
    }
 
    public static void Main()
    {
        int n = 13;
        Console.Write(repUnitValue(n));
    }
}
 
// This code is contributed by Sam007.

<?php
// PHP program to find least value of
// k for which R(k) is divisible by n
function repUnitValue($n)
{
     
    // To check n is coprime or not
    if ($n % 2 == 0 || $n % 5 == 0)
        return 0;
 
    // to store R(k) mod n
    // and 10^k mod n value
    $rem = 1;
    $power = 1;
    $k = 1;
    while ($rem % $n != 0)
    {
        $k++;
        $power = $power * 10 % $n;
        $rem = ($rem + $power) % $n;
    }
     
    return $k;
}
 
    // Driver Code
    $n = 13;
    echo repUnitValue($n);
     
// This code is contributed by aj_36
?>

<script>
 
 
// java script program to find least value of
// k for which R(k) is divisible by n
function repUnitValue(n)
{
     
    // To check n is coprime or not
    if (n % 2 == 0 || n % 5 == 0)
        return 0;
 
    // to store R(k) mod n
    // and 10^k mod n value
    let rem = 1;
    let power = 1;
    let k = 1;
    while (rem % n != 0)
    {
        k++;
        power = power * 10 % n;
        rem = (rem + power) % n;
    }
     
    return k;
}
 
    // Driver Code
    let n = 13;
    document.write(repUnitValue(n));
     
// This code is contributed by sravan kumar.
 
</script>

6

Complejidad temporal: O(n)

Espacio Auxiliar: O(1)