정수론

나머지의 특징

나머지의 순환

 우리는 0이상의 양의 정수 n의 나머지 a와 몫 b에 대하여 아래와 같은 표현을 사용할 수 있습니다.

  n = ax + b (단, 0 <= b < a)

 위와 같은 식에서 몫을 a라고 한다면, b는 [0, a-1]의 범위 안에 존재하게 됩니다. 또한 n이 1씩 증가할수록 b는 차례로 1씩 증가하다가 0으로 돌아오고, 다시 증가하고를 반복합니다. 즉, n이 차례로 증가할 때 마다 나머지 b[0, a-1]범위를 순환하게 됩니다.

 아래의 문제들은 나머지의 순환성을 이용하면 풀 수 있는 문제들입니다. 한 번 풀이를 생각해보시길 바랍니다.

나머지 뿐만 아니라 다양한 수들의 순환성에 대한 토픽은 나중에 따로 작성하도록 하겠습니다.

[연습 문제 1]

N(1 ≤ N ≤ 2, 000, 000)은 사람의 수를 뜻하며, i번째 사람의 나이는 다음의 공식을 통해 구할 수 있다.

Xi+1 = (11Xi+97) mod 100

이 때 모든 사람의 나이를 오름차순으로 정렬하였을 때 P번째 사람의 나이를 계산하시오.

 

제출 및 채점 : http://judge.lavida.us/problem.php?id=2103

 

[연습 문제 2]

 임의의 여섯개의 정수 X1, X2, X3, P1, P2, P3,가 있다. 아래의 조건을 만족하는 가장 작은 정수 N을 찾으시오. 

  N을 P1으로 나눈 나머지가  X1 (X1 < P1)

  N을 P2으로 나눈 나머지가  X(X2 < P2)

  N을 P3으로 나눈 나머지가  X(X3 < P3)

( 0 <= Xi  <=300 )

( 1 <= Pi <=300 )

( 0 <= N <= 1,000,000,000 )

 

제출 및 채점 : http://judge.lavida.us/problem.php?id=1010

 

나머지의 법칙

 나머지 연산은 기본적으로 결합, 분배, 교환법칙이 모두 성립하지 않습니다. 그래서 사용할때에 항상 계산순서와 위치에 주의를 해야합니다. 단 나머지 연산에서 성립하는 독특한 성질들도 있습니다. 

 a를 b로 나눈 나머지를 a mod b = a % b라고 표현하기로 합시다. 이 때 나머지는 다음과 같은 식들이 항상 성립합니다. 

 ( a + m ) % m = a % m

 ( (a % m) + ( b % m) ) % m = ( a + b ) % m 

 ( ( a % m) * ( b % m) ) % m = ( a * b) % m 

 

 

나머지의 역방향 계산법 

 주로 환형 큐(Circular Queue)와 같이 인덱스가 순환하는 구조에 자주 사용되는 방법입니다. 아래와 같은 원판을 상상 해 봅시다. 

 현재 우리가 a칸에 서 있다고 가정할 때에 b칸 만큼 앞으로 전진했을 때 서 있을 칸의 위치는 아래와 같이 간단하게 계산할 수 있습니다.

int next_step(int now,int len, int count)
{ //길이가 len인 원형 판에서 
  // now번 칸에 서 있을 때 count 칸 만큼 전진하면
  // 서 있게 되는 칸의 번호 계산하기
  return ( now + count ) % len;  
}

 

 그렇다면 반대로 b칸 만큼 뒤로 간 경우 서 있게 될 인덱스는 어떻게 계산할 수 있을까요? ba보다 작거나 같다면 바로 (a-b)%m번 칸에 서 있다는 것을 알 수 있지만, ba보다 큰 경우 (a-b)가 음수가 되어 음수 나머지가 발생하게 됩니다. 위 처럼 환형으로 순환하는 인덱스를 계산하고 싶을때에는 아래와 같이 구현하면 됩니다.

int back_step(int now, int len, int count)
{ //길이가 len인 원형 판에서
  //now번 칸에 서 있을 때 
  //count칸 만큼 후진한 후 서 있는 칸 번호
  return ( now - (count % len) + len ) % len;
}

 위처럼 계산할 수 있는 이유는 , 어차피 원형판위에 존재하는 칸의 개수 len번째마다 같은 위치에 서있게 되므로 결국 count칸 만큼 뒤로 간 결과는 (count % len)만큼 뒤로 간 결과와 같습니다. 이 때 (count % len)len보다 작으므로 여기에 len을 더해주면 최종적으로 len으로 나눈 나머지를 구했을 때 결과는 같지만,  len - (count % len)이 항상 양수이므로 양수만으로 계산을 할 수 있게 됩니다.

 

댓글

댓글 본문
작성자
비밀번호
버전 관리
코딩몬스터
현재 버전
선택 버전
graphittie 자세히 보기