[BOJ] 1009번: 분산처리

1009번: 분산처리

풀이

를 해주면 된다. 하지만 long long형도 100^1000000까지는 저장하지 못하기 때문에 그리고 우리의 목적에만 두자면 굳이 a^b를 계산한 후 %10을 할 필요가 없고 연산 중간마다 %10 연산을 해주면 된다.

또한 단순히 반복문을 돌려서 계산해도 되지만 제곱의 성질인 을 이용하면 훨씬 더 빠른 연산이 가능하다. 이 연산에 대한 설명은 여기를 눌러서 확인하길 바란다.

코드

#include <cstdio>
 
int pow(int a, int b)
{
    int ans = 1;
    while (b) {
        if (b & 1) ans = (ans * a) % 10;
        a = (a * a) % 10;
        b >>= 1;
    }
    return ans;
}
 
int main()
{
    int T;
    scanf("%d", &T);
    for (int i = 0, a, b; i < T; ++i) {
        scanf("%d %d", &a, &b);
        printf("%d\n", (pow(a, b) + 9) % 10 + 1);
    }
    return 0;
}