[TIL #11] 나머지가 1이 되는 수 찾기

나머지가 1이 되는 수는,

어떤 정수 $n$을 모듈러 연산을 했을 때 그 값이 1인 수를 뜻한다.

식으로 표현하면 다음과 같다.

$$n\,mod\,x=1$$

 

 그리고 이걸 구하는 가장 단순한 방법은 다음과 같다.

 

int solution(int n) {
    for(int i=2; i<n;++i)
        if(n%i==1) return i;
    return n-1;
}

2부터 시작하여 나머지가 1이 남는 수를 전체의 경우의 수를 순회하며 찾는다.

 

하지만 난 이 방법이 맘에 안 들었다.

좀 더 괜찮은 방법을 찾아보기로 했다.

 

$$n\,mod\,x=1$$

위 식은 다음과 같이 표현할 수 있다.

 

$$n - 1\,mod\,x=0$$

즉 $x$는 $n-1$의 약수여야 한다.

따라서, $n-1$의 약수 중 가장 작은 값을 찾으면 된다.

 

이를 코드로 작성하면 다음과 같다.

#include <cmath>

int solution(int n) {    
    int target = n - 1;
    for(int i = 2; i <= std::sqrt(target); i++)
        if (target % i == 0)
            return i;
    
    return target;
}

 

약수를 활용하는 것은 다음의 글에서 해 본 것이다.

[TIL #10] 자릿수 더하기 / 약수의 합

 

약수의 대칭성을 활용하여 최악의 경우 $O(\sqrt{n})$의 시간복잡도를 가지게 되었다.

단순한 방식이 $O(n)$의 시간복잡도를 가지는 것에 비해 대단히 효율적이다.

$n$이 1,000,000이라면 999,999번 확인해야 하지만,

약수의 성질을 활용하면 최대 999번으로 끝난다.

 

역시 배워두면 어딘가 써먹는다.