[백준] - 분산처리 - 복습

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

몇 연승을 하든 나머지로 나오는 값은 반복되고
계산 중간에는 나머지만 활용하면 된다(굳이 전체 값을 계산할 필요가 없음)

좀 더 나아가서 전체를 절반으로 나누어 해당 연승까지의 mod연산값끼리의 mod값을 구해도 된다

3 * 3 * 3 * 3 % 10 = 1
나머지 9 나머지 9
9 * 9 % 10 = 1

#include <iostream>
#include <math.h>

using namespace std;

//int powermod(int a, int b, int n)
//{
//    int r = 1;
//    for (int i = 0; i < b; i++)
//        r = r * a%n;
//
//    return r;
//}

int powermod(int a, int b, int n)
{

    if (b == 1) {
        return a%n;
    }
    int h = powermod(a, b / 2, n);
    h = h * h%n;
    if ((b & 1) == 1) { //odd number
        h = h * a%n;
    }
    return h;
}

int main()
{
    int testcase;
    cin >> testcase;
    for (int t = 0; t < testcase; t++)
    {
        int a, b;
        cin >> a >> b;

        int result = powermod(a, b, 10);
        if (result == 0)
            result = 10;

        printf("%d\n", result);
    }
}