(Java) Project Euler 026 - Reciprocal Cycles

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

//      1/2 = 0.5
//      1/3 = 0.(3)
//      1/4 = 0.25
//      1/5 = 0.2
//      1/6 = 0.1(6)
//      1/7 = 0.(142857)
//      1/8 = 0.125
//      1/9 = 0.(1)
//      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.

 

public class ProjectEuler_026 {
    public static void main(String[] args) {
        // 가장 긴 순환 주기와 그때의 d 값을 저장하는 변수
        int longestCycle = 0;
        int result = 0;

        // 2부터 999까지 d에 대해 순환 주기 계산
        for (int d = 2; d < 1000; d++) {
            int cycleLength = getCycleLength(d);

            // 현재 계산된 순환 주기가 가장 긴 경우 갱신
            if (cycleLength > longestCycle) {
                longestCycle = cycleLength;
                result = d;
            }
        }

        // 결과 출력
        System.out.println("The value of d < 1000 with the longest recurring cycle is: " + result);
    }

    // 주어진 d에 대한 순환 주기 계산
    static int getCycleLength(int d) {
        // 나머지를 저장하는 배열
        int[] remainders = new int[d];
        int remainder = 1;
        int position = 0;

        // 나머지가 0이거나 이미 저장된 경우까지 반복
        while (remainders[remainder] == 0 && remainder != 0) {
            // 현재 나머지의 위치 저장
            remainders[remainder] = position;
            // 나머지 갱신
            remainder = (remainder * 10) % d;
            // 위치 증가
            position++;
        }

        // 나머지가 0인 경우 순환 주기 없음을 의미
        return remainder == 0 ? 0 : position - remainders[remainder];
    }
}