026. Reciprocal Cycles (단위 분수의 순환소숫값이 가장 긴 것 찾기)

​문제 (English)

A unit fraction contains 1 in the numerator. The decima representation of the unit fractions with denominators 2 to 10 are given: 

 

$$ \frac {1}{2} = 0.5$$

$$ \frac {1}{3} = 0.(3)$$

$$ \frac {1}{4} = 0.25$$

$$ \frac {1}{5} = 0.2$$

$$ \frac {1}{6} = 0.1(6)$$

$$ \frac {1}{7} = 0.(142857)$$

$$ \frac {1}{8} = 0.125$$

$$ \frac {1}{9} = 0.(1)$$

$$ \frac {1}{10} = 0.1$$

 

Where 0.1(6) means 0.166666..., and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle.

Find the value of d < 1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.

 

Answer: 983

문제 분석

---

분자가 1인 단위함수를 소수로 나타냈을 때, 순환소수가 되는 경우, 순환되는 자릿수가 가장 긴 수를 찾는 문제.

 

실제 수를 나눠가면서, 순환소수의 첫 번째 수가 나오는 두 번째 자릿수를 찾으면 되겠다.

어떤 수 i에 대해, 몫과 나머지를 차례로 구해보면, 처음수는 무조건 10을 곱해서 i로 나눠줘야 한다. 그다음은 나머지에 대해서 i로 나누는 것 반복

 

i=2: (q,r) = (10/2=5, 10%2=0) --> 나머지기 0이므로 순환 없음

i= 3:  (q,r) = (10/3=3, 10%3=1) > (10/3=3, 10%3=1)  --> 동일한 것이 나왔기에 순환소수이고, 순환 사이클은 1

i=4: (q,r) = (10/4=2, 10%4=2) > (20/4=5, 20%4=0) --> 순환 없음

i=5: (q,r) = (10/5=2, 10%5=0) --> 순환 없음

i=6: (q,r) = (10/6=1, 10%6=4) > (40/6=6, 40%6=4)  --> 나머지가 4로 동일한 것이 나왔기에 순환소수이고, 순환사이클은 1

 

지금까지 보면, 굳이 몫을 구할 필요없음을 알 수 있다. 나머지만 구하면 된다.

 

풀이 1 

---

어떤 단위함수 1/d에 대해서, 순환 사이클 길이를 구하는 코드를 짜보자. 

d로 계속해서 나눠가면서 나머지를 구하고, 해당 나머지가 나온 적이 있는지를 확인하면 된다. 여기서, 몫을 굳이 구해서 몫이 같은지 확인할 필요가 없다. 나머지가 같으면 몫도 같은 것이 되는 것이기에 그런 것이고, 나머지는 그다음 스텝에서 d로 나눠지게 될 값이기에 어차피 구해야 하기에, 몫이 아닌 나머지만 구해서 사용한다.

#[cfg(test)]
fn recur(d:usize) -> usize {    
    let mut k = vec![1];
    let mut i = 0;  let mut j;      
    loop {
        i += 1;
        j = 10 * k[k.len()-1] % d; //only % -> no need to calculate / d
        if k.contains(&j) {break;}
        k.push(j);        
    }
    return i - k.iter().position(|&x| x==j).unwrap();
}

코드에서, 나머지의 시퀀스를 계속 저장하기 위해 벡터 v를 사용했고, 사용되었는지를 확인하기 위해 k.contains를 사용했다.

 

이제, 어떤 수 n이 주어졌을 때, n보다 작은 수중에서 순환 사이클이 가장 긴 수는, 4.. n까지의 모든 수에 대해 recur() 함수로 사이클 수를 구하면서, 가장 max가 될 때의 수를 찾으면 된다.

#[test]
fn test(){
    assert_eq!(3, answer(4));
    assert_eq!(3, answer(5));
    assert_eq!(3, answer(6));
    assert_eq!(3, answer(7));
    assert_eq!(3, answer(7));
    assert_eq!(7, answer(8));
    assert_eq!(983, answer(1000));
    assert_eq!(9967, answer(10000));

}

#[cfg(test)]
// return d < n, for which 1/d contains the longest recurring cycle
// 4 <= n <= 10000
fn answer(n:usize) -> usize{
    if n < 4 {return 0;}

    let mut max = 1;
    let mut max_i =3; 
    for i in 4..n {
        let cnt = recur(i);
        if cnt > max {
            max=cnt;
            max_i=i;
        }
    }

    return max_i;
}

 

풀이 2 

---

풀이 1 코드에서 최적화할 요소들이 있다.

 

• 짝수의 경우는 순환소수가 되지 않기에, 홀수에 대해서만 순환소수 사이클을 조사하면 되겠다.
• 나머지가 0이 나오는 경우는 순환소수가 아니기에, 나머지값이 벡터에 있는지 조사하지 않아도 되겠다.
• 나머지를 시퀀스로 저장해 놓고, 현재 계산된 나머지가 해당 벡터에 있는지를 찾는 방식은, 찾을 때마다 벡터의 해당 길이만큼 뒤져야 하기에 비효율적이다. 아예 나머지가 나올 수 있는 공간인 d 만큼 배열을 선언해 놓고, 해당 나머지값이 나왔었는지 아닌지를 체크하는 형태로 하면, 상수 시간에 나머지가 있었는지를 확인할 수 있겠다.

위 최적화 방안을 적용한 코드는 아래와 같다.

 

#[test]
fn test1(){
    assert_eq!(3, answer1(4));
    assert_eq!(3, answer1(5));
    assert_eq!(3, answer1(6));
    assert_eq!(3, answer1(7));
    assert_eq!(3, answer1(7));
    assert_eq!(7, answer1(8));
    assert_eq!(983, answer1(1000));
    assert_eq!(9967, answer1(10000));
}

#[cfg(test)]
// return d < n, for which 1/d contains the longest recurring cycle
// 4 <= n <= 10000
fn answer1(n:usize) -> usize{
    if n < 4 {return 0;}

    let mut max = 1;
    let mut max_i =3; 
    for i in (5..n).step_by(2) {
        let cnt = recur1(i);
        if cnt > max {
            max=cnt;
            max_i=i;
        }
    }
    return max_i;
}

#[cfg(test)]
fn recur1(d:usize) -> usize {    
    let mut k = vec![None; d]; // to check residual exist or not 
    let mut i = 0;  
    let mut j = 1;   
    loop {
        i += 1;
        j = 10 * j % d; //only % -> no need to calculate / d
        if j==0 {return 0;}
        match k[j]{
            Some(idx) => {return (i - idx) as usize;},
            None => k[j] = Some(i),
        }               
    }    
}

 

풀이 3

---

순환소수의 사이클 길이가 큰 수의 특징은, 모두 소수라는데 있다. 따라서, n보다 작은 소수를 모두 찾은 후, 이 소수에 대해서만 조사해도 된다. 수행 속도가 좀 더 빨라진다.

 

//--------------------
//only use prime numbers. 
#[test]
fn test2(){
    assert_eq!(3, answer2(4));
    assert_eq!(3, answer2(5));
    assert_eq!(3, answer2(6));
    assert_eq!(3, answer2(7));
    assert_eq!(3, answer2(7));
    assert_eq!(7, answer2(8));
    assert_eq!(983, answer2(1000));
    assert_eq!(9967, answer2(10000));
}


#[cfg(test)]
// return d < n, for which 1/d contains the longest recurring cycle
// 4 <= n <= 10000
fn answer2(n:usize) -> usize{
    if n < 4 {return 0;}

    //eratostenes seive
    let mut seive = vec![0;n+1];
    seive[0]=1; seive[1]=0;
    let sqrt_n = (n as f64).sqrt() as usize;
    for i in 2..=sqrt_n {
        if i > 2 && i % 2 == 0 {continue;}
        for j in (2*i..=n).step_by(i){ seive[j] = 1;}
    }

    let mut max = 1;
    let mut max_i =3; 
    for i in (5..n).step_by(2) {
        if seive[i] == 1 {continue;} //if not prime, no need to calculate
        let cnt = recur1(i);
        if cnt > max {
            max=cnt;  max_i=i;
        }
    }
    return max_i;
}

풀이 4

---

hackerrank 사이트는, 위 풀이 방법으로 속도를 최적화해도, 통과가 잘 안 된다. 

각 문제 케이스가 나오기 전에, 미리 n <= 100000개에 대해서 사이클 길이가 가장 큰 값을 미리 저장 두고, 문제에 대해서는 미리 구한 값을 답해야만, 통과할 수 있다.

 

미리 어떤 수 d에 대해서, d보다 작으면서 사이클 길이가 가장 긴 수를 구하는 코드는 아래와 같다.

#[cfg(test)]
// n 미만 정수에 대해, recu가 최소가되는 값을 저장한 벡터 리턴
fn get_max_recu(n:usize) -> Vec<usize> {
    let mut v:Vec<usize> = vec![0;n+1];
    let mut max = 1;
    let mut max_i =3; 
    for i in 4..=n {
        v[i] = max_i;
        let cnt = recur1(i);
        if cnt > max {
            max=cnt;
            max_i=i;
        }
    }
    return v;
}

 

이 함수를 이용해서 실제 문제 풀이하는 코드는, 

use std::io::{self, BufRead};
fn main() {
    let stdin = io::stdin();
    let mut it = stdin.lock().lines();
    let t = it.next().unwrap().unwrap().trim().parse::<usize>().unwrap();
    let v = get_max_recu(10000);
    for _ in 0..t {
        let n = it.next().unwrap().unwrap().trim().parse::<usize>().unwrap();
        println!("{}",answer3(n, &v));
    }
}
fn get_max_recu(n:usize) -> Vec<usize> {
    let mut v:Vec<usize> = vec![0;n+1];
    let mut max = 1;
    let mut max_i =3; 
    for i in 4..=n {
        v[i] = max_i;
        let cnt = recur3(i);
        if cnt > max {
            max=cnt;
            max_i=i;
        }
    }
    return v;
}

fn answer3(n:usize, v:&Vec<usize>) -> usize{
    return v[n];
}

fn recur3(d:usize) -> usize {    
    let mut k = vec![None; d]; // to check residual exist or not 
    let mut i = 0;  
    let mut j = 1;   
    loop {
        i += 1;
        j = 10 * j % d; //only % -> no need to calculate / d
        if j==0 {return 0;}
        match k[j]{
            Some(idx) => {return (i - idx) as usize;},
            None => k[j] = Some(i),
        }               
    }    
}

 

총평

---

구해진 나머지를 어떻게 보관했다가, 중복되는 나머지를 어떻게 효율적으로 찾는지를 연습하게 하는 문제이다.

 

hackerrank의 문제는, 미리 답을 찾아놓고 각 문제마다는 미리 구한 해답을 상수 시간에 리턴하지 않고는 통과되지 않는다. 

 

전체 소스코드

---

p26.rs 

#[test]
fn test(){
    assert_eq!(3, answer(4));
    assert_eq!(3, answer(5));
    assert_eq!(3, answer(6));
    assert_eq!(3, answer(7));
    assert_eq!(3, answer(7));
    assert_eq!(7, answer(8));
    assert_eq!(983, answer(1000));
    assert_eq!(9967, answer(10000));

}

#[cfg(test)]
// return d < n, for which 1/d contains the longest recurring cycle
// 4 <= n <= 10000
fn answer(n:usize) -> usize{
    if n < 4 {return 0;}

    let mut max = 1;
    let mut max_i =3; 
    for i in 4..n {
        let cnt = recur(i);
        if cnt > max {
            max=cnt;
            max_i=i;
        }
    }

    return max_i;
}

//if d=2, j={10%2=0, 0%2=0}, return 2-1=1
//if d=3, j={10%3=1, 10%3=1}, return 2-1=1
//if d=4, j={10%4=2, 20%4=0, 0%4=0}, return 3-2=1
//if d=6, j={10%6=4, 40%6=4}, return 2-1=1
//if d=7, j={10%7=3, 30%7=2, 20%7=6, 60%7=4, 40%7=5, 50%/7=1, 10%7=3}, return 7-1=6
#[cfg(test)]
fn recur(d:usize) -> usize {    
    let mut k = vec![1];
    let mut i = 0;  let mut j;      
    loop {
        i += 1;
        j = 10 * k[k.len()-1] % d; //only % -> no need to calculate / d
        if k.contains(&j) {break;}
        k.push(j);        
    }
    return i - k.iter().position(|&x| x==j).unwrap();
}

//---------------------
// only do odd number, recur 없으면 return 0, residual저장방식 변경
#[test]
fn test1(){
    assert_eq!(3, answer1(4));
    assert_eq!(3, answer1(5));
    assert_eq!(3, answer1(6));
    assert_eq!(3, answer1(7));
    assert_eq!(3, answer1(7));
    assert_eq!(7, answer1(8));
    assert_eq!(983, answer1(1000));
    assert_eq!(9967, answer1(10000));
}

#[cfg(test)]
// return d < n, for which 1/d contains the longest recurring cycle
// 4 <= n <= 10000
fn answer1(n:usize) -> usize{
    if n < 4 {return 0;}

    let mut max = 1;
    let mut max_i =3; 
    for i in (5..n).step_by(2) {
        let cnt = recur1(i);
        if cnt > max {
            max=cnt;
            max_i=i;
        }
    }
    return max_i;
}

#[cfg(test)]
fn recur1(d:usize) -> usize {    
    let mut k = vec![None; d]; // to check residual exist or not 
    let mut i = 0;  
    let mut j = 1;   
    loop {
        i += 1;
        j = 10 * j % d; //only % -> no need to calculate / d
        if j==0 {return 0;}
        match k[j]{
            Some(idx) => {return (i - idx) as usize;},
            None => k[j] = Some(i),
        }               
    }    
}


//--------------------
//only use prime numbers. 
#[test]
fn test2(){
    assert_eq!(3, answer2(4));
    assert_eq!(3, answer2(5));
    assert_eq!(3, answer2(6));
    assert_eq!(3, answer2(7));
    assert_eq!(3, answer2(7));
    assert_eq!(7, answer2(8));
    assert_eq!(983, answer2(1000));
    assert_eq!(9967, answer2(10000));
}


#[cfg(test)]
// return d < n, for which 1/d contains the longest recurring cycle
// 4 <= n <= 10000
fn answer2(n:usize) -> usize{
    if n < 4 {return 0;}

    //eratostenes seive
    let mut seive = vec![0;n+1];
    seive[0]=1; seive[1]=0;
    let sqrt_n = (n as f64).sqrt() as usize;
    for i in 2..=sqrt_n {
        if i > 2 && i % 2 == 0 {continue;}
        for j in (2*i..=n).step_by(i){ seive[j] = 1;}
    }

    let mut max = 1;
    let mut max_i =3; 
    for i in (5..n).step_by(2) {
        if seive[i] == 1 {continue;} //if not prime, no need to calculate
        let cnt = recur1(i);
        if cnt > max {
            max=cnt;  max_i=i;
        }
    }
    return max_i;
}


//---------------------
// 미리 구해뒀다가 답변
#[test]
fn test3(){
    let v = get_max_recu(10000);
    // println!("{:?}",v);

    assert_eq!(3, answer3(4, &v));
    assert_eq!(3, answer3(5, &v));
    assert_eq!(3, answer3(6, &v));
    assert_eq!(3, answer3(7, &v));
    assert_eq!(3, answer3(7, &v));
    assert_eq!(7, answer3(8, &v));
    assert_eq!(983, answer3(1000, &v));
    assert_eq!(9967, answer3(10000, &v));
}

#[cfg(test)]
// n 미만 정수에 대해, recu가 최소가되는 값을 저장한 벡터 리턴
fn get_max_recu(n:usize) -> Vec<usize> {
    let mut v:Vec<usize> = vec![0;n+1];
    let mut max = 1;
    let mut max_i =3; 
    for i in 4..=n {
        v[i] = max_i;
        let cnt = recur1(i);
        if cnt > max {
            max=cnt;
            max_i=i;
        }
    }
    return v;
}

#[cfg(test)]
// return d < n, for which 1/d contains the longest recurring cycle
// 4 <= n <= 10000
fn answer3(n:usize, v:&Vec<usize>) -> usize{
    return v[n];
}

//----------------
//primes만 미리 구해서 사용
#[test]
fn test4(){
    let v = get_primes(10000);
    // println!("{:?}",v);

    assert_eq!(3, answer4(4, &v));
    assert_eq!(3, answer4(5, &v));
    assert_eq!(3, answer4(6, &v));
    assert_eq!(3, answer4(7, &v));
    assert_eq!(3, answer4(7, &v));
    assert_eq!(7, answer4(8, &v));
    assert_eq!(983, answer4(1000, &v));
    assert_eq!(9967, answer4(10000, &v));
}

#[cfg(test)]
//find all primes <= n
fn get_primes(n:usize) -> Vec<usize> {
    //1. sieve
    let mut sieve:Vec<usize> = vec![1; n+1];
    sieve[0]=0; sieve[1]=0;
    let sqrt_n = (n as f64).sqrt() as usize;
    for i in 2..=sqrt_n {
        for j in (2*i..=n).step_by(i) {
            sieve[j] = 0;
        } 
    }
    //2. primes
    let mut primes:Vec<usize> = Vec::new();
    for i in 2..sieve.len() {
        if sieve[i] == 1 {primes.push(i);}
    }
    return primes;
}

#[cfg(test)]
// return d < n, for which 1/d contains the longest recurring cycle
// 4 <= n <= 10000
fn answer4(n:usize, primes:&Vec<usize>) -> usize{
    if n < 4 {return 0;}

    let mut max = 1;
    let mut max_i =3; 
    for i in primes {
        if *i < 4 { continue;}
        if *i >= n { break; }
        let cnt = recur1(*i);
        if cnt > max {
            max=cnt;  max_i = *i;
        }
    }
    return max_i;
}

 

끝