Đề bài
Một số được gọi là số tự đẳng cấu (automorphic) nếu bình phương của nó tận cùng bằng đúng các chữ số của số đó. Ví dụ, 76² = 5776, tận cùng là 76, nên 76 là số tự đẳng cấu.
Hãy viết automorphic_number(n).
n² có thể lớn tới 10^18, vẫn vừa trong kiểu số nguyên có dấu 64 bit. Bạn có thể so sánh từng chữ số từ phải sang, hoặc so sánh n² mod 10^d với n, trong đó d là số chữ số của n.
Đầu vào
n: Số cần kiểm tra.
Đầu ra
Trả về true nếu các chữ số cuối của n² đúng bằng các chữ số của n, ngược lại trả về false. 0 và 1 là số tự đẳng cấu (0² = 0, 1² = 1).
Ràng buộc
0 ≤ n ≤ 10^9
Ví dụ
Đầu vào:
n = 25
Kết quả mong đợi:
expected = True
Đầu vào:
long long n = 25;
Kết quả mong đợi:
bool expected = true;
Đầu vào:
long n = 25;
Kết quả mong đợi:
bool expected = true;
Giải thích
25² = 625, tận cùng là 25, nên kết quả là true.
Đầu vào:
n = 7
Kết quả mong đợi:
expected = False
Đầu vào:
long long n = 7;
Kết quả mong đợi:
bool expected = false;
Đầu vào:
long n = 7;
Kết quả mong đợi:
bool expected = false;
Giải thích
7² = 49, tận cùng là 9 chứ không phải 7, nên kết quả là false.
Hướng tiếp cận
Hãy tự thử trước, sau đó mở từng gợi ý một.
Gợi ý 1
Tìm xem n có bao nhiêu chữ số.
Gợi ý 2
d chữ số cuối của một số chính là số dư khi chia nó cho 10^d.
Gợi ý 3
Nhớ coi n = 0 là số có một chữ số, để 10^d bằng 10 chứ không phải 1.
Độ phức tạp mong đợi
thời gian O(d) với d chữ số, bộ nhớ phụ O(1)
Tham khảo
Thử thách này đã được điều chỉnh cho CodeUtility. Hãy làm theo đề bài và các ràng buộc ở trên.