Hướng dẫn cho POWER
Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
Spoiler Alert
Hint 1
Tính toán tìm số cuối cùng, các chữ số khác mình không quan tâm mình có thể lấy mod 10 sau mỗi phép tính
Hint 2
Việc tính x ^ n % m có thể tính trong O(log n)
- x = x ^ (n / 2) * x ^ (n / 2) * x ^ (n % 2)
Hint 3
Để ăn sub cuối, bạn phải có nhận xét toán học
- Mình chỉ quan tâm số cuối, nên trong xâu đầu mình lấy kí tự cuối cùng: (x ^ n) % 10 = ((x % 10) ^ n) % 10
- Việc tính x ^ n % 10 có chu trình tối đa là 4, ta có thể tiền xử lí mảng này theo toán học
Reference AC code | O(1) time | O(1) auxiliary space | Math
C++
vector<vector<int> > G {
{0, 0, 0, 0},
{1, 1, 1, 1},
{6, 2, 4, 8},
{1, 3, 9, 7},
{6, 4, 6, 4},
{5, 5, 5, 5},
{6, 6, 6, 6},
{1, 7, 9, 3},
{6, 8, 4, 2},
{1, 9, 1, 9}
};
int main()
{
string s;
cin >> s;
int x = s.back() - '0'; /// a % 10
cin >> s;
int y = s.back() - '0'; /// b % 10
if (s.size() >= 2) y += 10 * (s[s.size() - 2]); /// b % 100
cout << (y == 0 ? 1 : G[x][y % 4]);
return 0;
}
Bình luận
NGÔN ngữ gì đây a ơi
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.