[백준] 1009. 분산처리

: solved.ac - bronze 2

https://www.acmicpc.net/problem/1009

1009번: 분산처리

 

 

예제 입력

5
1 6
3 7
6 2
7 100
9 635

 

예제 출력

1
7
6
1
9

 

정답

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
	int t, a, b, com;
	scanf("%d", &t);

	for (int i = 0; i < t; i++) {
		scanf("%d %d", &a, &b);

		com = a;
		b = b % 4 + 4;

		for (int j = 0; j < b-1; j++) {
			com = (com * a) % 10;
		}

		if (com == 0) com = 10;
		printf("%d\n", com);
	}

	return 0;
}

---

해설

: 자연수가 거듭제곱될 때 1의 자리 수가 일정 규칙 내에서 변화하는 특성을 이용한다.

 

제시되는 지수의 범위가 상당히 크기 때문에 프로그램 내에서 실제로 수를 곱하게끔 하면 반드시 오버플로우가 나게 되어 있다. long long int 형도 100의 1000000제곱을 감당할 수는 없다.

대신 우리가 구해야 하는 것은 1의 자리뿐이기 때문에, 수를 곱하고 -> 1의 자리를 자르고 -> 다시 수를 곱하고의 동작을 반복하는 식으로 1의 자리를 구한다.

 

 

이때 거듭제곱할 지수가 되는 b 값을 약간 조정해 준다. 통상적으로 1의 자리 수들은 거듭제곱할 경우 최대 4번을 주기로 같은 1의 자리 수가 반복되기 때문에, 4번 곱하는 것과 100번 곱하는 것이 1의 자리에 한정해서는 같은 효과를 가진다. 때문에 b를 4로 나누어 그 나머지를 구한다. 이때 나머지가 0이 되는 경우를 방지하기 위해 4를 더해 준다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int main() {
	int t, a, b, com;
	scanf("%d", &t);

	for (int i = 0; i < t; i++) {
		scanf("%d %d", &a, &b);

		com = a;
		b = b % 4 + 4;

 

결과값인 com에 이미 a가 설정되어 있기 때문에 한 번 곱해져 있는 것으로 간주하고,

b-1번 동안 a를 곱하고->1의 자리를 구하는 동작을 반복한다.

만약 1의 자리가 0일 경우 0번 컴퓨터가 아닌 10번 컴퓨터가 배정되므로 이 경우만 if문으로 별도 처리해 주고

도출된 결과를 출력한다.

		for (int j = 0; j < b-1; j++) {
			com = (com * a) % 10;
		}

		if (com == 0) com = 10;
		printf("%d\n", com);
	}

	return 0;
}