[Javascript][BOJ] 1009 분산처리

www.acmicpc.net/problem/1009

1009번: 분산처리

분명히 쉬운문제 같은데 매우 풀기 까다로운 문제였다. 

당장 내일 같은 문제를 만단다더라도 헷갈릴것같다.

 

핵심아이디어

a**b개의 데이터를 1~10번 컴퓨터로 차례로 처리할 때,

마지막 데이터는 몇번 컴퓨터가 처리하는가를 묻는 문제이다.

컴퓨터는 총 10대이므로, a**b가 1이면 1번컴퓨터, 20이면 10번컴퓨터, 115면 5번컴퓨터가 마지막 컴퓨터가 된디ㅏ.

즉, a**b의 1의자리 값만 알면 마지막 데이터를 처리하는 컴퓨터를 알 수 있다.

일단 a**b최대값이 엄청날 것이므로 무작정 a**b % 10 를 시전해서는 안된다.

for문으로 (a*a)%10를 b번 반복해주자니 b가 안그래도 1000000까지인데, T도 많을 수 있으므로 시간초과가 날것이라서 안된다.

 

같은 숫자를 계속 곱하는 행위는 1의자리 숫자를 반복하게 만든다는 특징을 이용한다.

1**b는 1,1,1,1,1....

2**b는 2,4,8,6,2....

3**b는 3,9,7,1,3...

4**b는 4,6,4,6,4....

5**b는 5,5,5,5,5....

6**b는 6,6,6,6,6,.....

7**b는 7,9,3,1,7...

8**b는 8,4,2,6,8,...

9**b는 9,1,9,1,9....

0**b는 0,0,0,0,0....

 

위 규칙을 보면 알 수 있듯이, 같은 숫자를 곱하는 것은 4번째마다 같은 1의 자리 숫자가 나옴을 알 수 있다.

즉, b가 매우큰 숫자라도 최대 4번만 사용한다면, 같은 효과를 누릴 수 있으므로,
매우적은 b만큼의 for문을 통해 정답을 구할 수 있다.

 

 

 

const readline = require('readline');
const rl = readline.createInterface({
	input: process.stdin,
	output: process.stdout,
});

const solution = function (input) {
	const _ = parseInt(input.shift());
	let ans = '';
	for (row of input) {
		let [a, b] = row.split(' ').map((e) => parseInt(e));
		let res = a%10 === 0 ? 10 : a%10;
		b = (b % 4) === 0 ? 4 : b%4;
		for (let i = 2; i <= b; i++) {
			res = (res * a) % 10;
			res = res === 0 ? 10 : res;
		}
		ans += `${res}\n`;
	}
	console.log(ans.trim('\n'));
};

const input = [];
rl.on('line', function (line) {
	input.push(line);
}).on('close', function () {
	solution(input);
	process.exit();
});