Tất cả thử thách
Dễ 0 đã giải Tỷ lệ chấp nhận 0%

Số tự đẳng cấu (Automorphic number)

Kiểm tra bình phương của một số có tận cùng bằng chính số đó hay không.

Bạn sẽ học được gì

  • Đếm số chữ số của một số
  • Lấy d chữ số cuối bằng phép chia lấy dư
  • Coi 0 là số có một chữ số

Đề bài

Xem bản gốc (English)

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ụ

Ví dụ 1
Đầ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.

Ví dụ 2
Đầ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.

Lời giải đạt tốt nhất của mỗi người. Lời giải nhanh hơn, tốn ít bộ nhớ hơn và được đánh giá cao hơn sẽ đứng trên.

Chưa có lời giải nào đạt. Giải bài này để giành hạng nhất.

Học hỏi từ người khác

Giải pháp cộng đồng

Chưa có giải pháp nào được chia sẻ. Hãy giải thử thách này để đăng giải pháp đầu tiên.