[BOJ] 백준 1009 분산처리

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

 Input 

5

1 6

3 7

6 2

7 100

9 635

 

 Output 

1

7

6

1

9

 

주먹구구 방식으로 구해봐야 1001000000 결과 자체를 저장하는 것은 쉽지 않습니다.

62 : 6 × 6 = 36 → 6번째 컴퓨터가 마지막 데이터 처리

 

75 : 7 × 7 × 7 × 7 × 7 = 16,807 → 7번째 컴퓨터가 마지막 데이터 처리

84 : 8 × 8 × 8 × 8 = 4,096 →  6번째 컴퓨터가 마지막 데이터 처리

▶ 곱해지는 결과에서 1의 자리가 무엇인지 중요합니다. ← 나머지 연산(%) 이용

 

숫자 저장자체는 가능해졌지만 연산 속도를 무시할 수는 없습니다.

※ 거듭 곱해지면서 1의 자릿수 변화

1: 1 → 1 → 1 → 1 ▶ 1 cycle 

2: 2 → 4 → 8 → 6 → 2 → 4 ▶ 4 cycle

3: 3 → 9 → 7 → 1 → 3 → 9 ▶ 4 cycle

4: 4 → 6 → 4 → 6 ▶ 2 cycle

5: 5 → 5 → 5 → 5 ▶ 1 cycle

6: 6 → 6 → 6 → 6 ▶ 1 cycle

7: 7 → 9 → 3 → 1 → 7 ▶ 4 cycle

8: 8 → 4 → 2 → 6 → 8 ▶ 4 cycle

9: 9 → 1 → 9 → 1 ▶ 2 cycle

결과적으로 어떤 숫자이든 4 cycle로 주기를 둔다고 할 수 있습니다.

▶ ab 에서 b = b % 4로 처리

* 주의: 코드상에서 0번째 컴퓨터는 10번째 출력

---

#include <iostream>
using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    int T; cin >> T;
    int a, b;
    while(T--){
        cin >> a >> b;
        int result = a % 10;
        int multiply = b % 4;

        for (int i = 1; i < (multiply == 0 ? 4 : multiply); i++){
            result *= a;
            result %= 10;
        }

        if(result == 0) 
            result = 10;

        cout << result << "\n";
    }
}