문제 풀이
9^635의 값은 long long 타입도 담을 수 없는 범위의 수이기 때문에, 모듈러를 이용해서 구해야 합니다.
각 숫자마다 제곱수를 만들다 보면, 맨 끝자리의 수가 똑같이 반복되는 구간을 발견할 수 있습니다.
반복되는 구간은 1제곱과 5 제곱이 같고, 2 제곱과 6 제곱이 같고, 3 제곱과 7 제곱이 같고, 4 제곱과 8 제곱이 같습니다.
반복되는 주기를 모듈러를 통해 b의 값을 최적화 시킨 후 답을 구하면 됩니다.
소스 코드
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int T;
cin >> T;
while (T--)
{
int a, b;
cin >> a >> b;
// 주기가 있다.
b = !(b % 4) ? 4 : b % 4;
int ans = 1;
while (b--) ans *= a;
if (ans % 10 == 0) cout << "10\n";
else cout << ans % 10 << '\n';
}
return 0;
}
'Algorithm' 카테고리의 다른 글
[백준 1110] 더하기 사이클 (0) | 2021.11.29 |
---|---|
[백준 2884] 알람 시계 (0) | 2021.11.29 |
[백준 16398] 행성 연결 (0) | 2021.11.22 |
[백준 16202] MST 게임 (0) | 2021.11.21 |
[백준 13905] 세부 (0) | 2021.11.20 |