9736번 - 정이면체군 다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 5 초 | 128 MB | 58 | 27 | 22 | 52.381% |
문제
정이면체군은 집합 D로, D상에서 곱셈 연산 *가 정의되어 있다. 집합 D는 두 원소 a와 b를 이용해 만들 수 있다. 곱셈 연산 *는 실제로 표기하는 경우는 거의 없고, 붙여서 쓰거나 제곱 형태로 나타낸다. 즉, a*a는 aa 또는 a2로 나타낸다. 또, a*a*b는 a2b1 또는 a2b로 나타낸다.
정이면체군 D는 두 파라미터 m과 n을 갖고, m ≥ 2, n ≥ 2이다. 이러한 정이면체군은 Dm,n으로 나타낸다. Dm,n사이의 관계는 다음과 같다.
am = a0 = 1, bn = b0 = 1, and ba = a(m-1)b.
따라서, Dm,n은 총 (mn)개의 원소를 가지며, 다음과 같다.
Dm,n = {ajbk | 0 ≤ j < m, 0 ≤ k < n} = {a0b0, a1b0, a2b0, ..., a(m-1)b0, ..., a(m-1)b(n-1)}.
예를 들어, m=6, n=2인 경우 D7,2는 다음과 같다.
{a0b0, a1b0, a2b0, a3b0, a4b0, a5b0, a6b0, a0b1, a1b1, a2b1, a3b1, a4b1, a5b1, a6b1}.
곱셉 연산은 교환 법칙이 성립하지 않기 때문에, ba ≠ ab이다. D7,2의 정의에 의하면 ba = a6b이다. 또, ajak = a(j+k)%m, bjbk = b(j+k)%n 이다. 따라서 다음과 같다.
(ajbk)(apbq) ≠ (a(j+p)%mb(k+q)%n)
D7,2의 두 원소 (a3b1)과 (a2b1)을 올바르게 곱하는 방법은 다음과 같다.
(a3b1)(a2b1) = (a3b0)(ba)(a1b1) = (a3b0)(a6b1)(a1b1)
ba = a6b이때문에 위와 같이 계산할 수 있다. 또, a3b0a6 = a3a6 = a(3+6)%7 = a2이기 때문에, (a3b0)(a6b1) = (a2b1)임을 알 수 있다. 따라서, 다음과 같이 계산할 수 있다.
(a3b0)(a6b1)(a1b1) = (a2b1)(a1b1).
이제, 위의 식을 아래와 같이 다시 계산할 수 있다.
(a2b1)(a1b1) = (a2b0)(ba)(a0b1) = (a2b0)(a6b1)(a0b1) = (a8b2) = (a1b0)
따라서, (a3b1)과 (a2b1)을 곱하면 (a3b1)(a2b1) = (a1b0)이 된다.
m과 n 그리고, 정이면체군 Dm,n 상의 두 원소 (ajbk)와 (apbq)가 주어졌을 때, 곱한 결과를 구하는 프로그램을 작성하시오.
입력
입력은 여러 개의 문제 세트로 이루어져 있다. 각 문제 세트는 입력 여러 줄로 이루어져 있다.
첫째 줄에는 문제ID와 m, n,p 가 주어지며, 공백으로 구분되어져 있다. m과 n은 1000을 넘지 않는 정수이고, p는 그 문제 세트에 있는 곱셈 문제의 개수이다. 다음 p개 줄에는 곱셈 문제가 주어지며, Dm,n 상의 두 원소가 주어진다. 각 원소는 a3b1형식이다. 각 문제 세트의 다음에는 바로 다음 문제 세트가 주어진다. 문제ID가 ZZ인 경우에는 입력의 끝을 나타낸다.
출력
각각의 곱셈 문제에 대해서, 다음을 출력한다.
ProblemID id: ajbk * apbq = arbs
id는 입력으로 주어진 문제ID, ajbk, apbq는 입력으로 주어진 두 원소, arbs는 결과이다.
예제 입력 1
C1 7 2 3 a3b1 a2b1 a5b1 a3b1 a2b1 a4b1 C2 9 3 2 a3b1 a2b1 a4b1 a3b1 ZZ 0 0 0
예제 출력 1
ProblemID C1: a3b1 * a2b1 = a1b0 ProblemID C1: a5b1 * a3b1 = a2b0 ProblemID C1: a2b1 * a4b1 = a5b0 ProblemID C2: a3b1 * a2b1 = a1b2 ProblemID C2: a4b1 * a3b1 = a1b2
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호