Editorial for POWER
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
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;
}
Comments
NGÔN ngữ gì đây a ơi
tiền xử lý mảng là sao dậy :))