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

Chu kỳ thập phân dài nhất

Tìm d không vượt quá giới hạn sao cho phân số 1/d có chu kỳ thập phân dài nhất.

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

  • Mô phỏng phép chia dài bằng các số dư
  • Phát hiện lặp lại bằng bảng tra cứu
  • Tính độ dài chu kỳ từ vị trí xuất hiện đầu tiên

Đề bài

Xem bản gốc (English)

Có những phân số đơn vị là số thập phân hữu hạn (1/4 = 0.25), số còn lại là số thập phân vô hạn tuần hoàn: 1/6 = 0.1666... lặp lại khối 1 chữ số, còn 1/7 = 0.142857142857... lặp lại khối 6 chữ số. Trong các giá trị d = 2, 3, ..., limit, hãy tìm d mà 1/d có khối lặp dài nhất. Hãy cài đặt phép chia dài như khi làm bằng tay: các chữ số bắt đầu lặp lại ngay khi một số dư xuất hiện trở lại.

Hãy viết longest_recurring_cycle(limit).

Đầu vào

limit: Mẫu số lớn nhất cần thử.

Đầu ra

Trả về d có khối lặp dài nhất. Phân số hữu hạn có độ dài khối lặp là 0. Nếu có nhiều d bằng nhau, trả về d nhỏ nhất.

Ràng buộc

2 ≤ limit ≤ 2000

Ví dụ

Ví dụ 1
Đầu vào:
limit = 8

Kết quả mong đợi:
expected = 7
Đầu vào:
long long limit = 8;

Kết quả mong đợi:
long long expected = 7;
Đầu vào:
long limit = 8;

Kết quả mong đợi:
long expected = 7;

Giải thích

Độ dài khối lặp với d từ 2 đến 8 là 0, 1, 0, 0, 1, 6, 0, nên đáp án là 7.

Ví dụ 2
Đầu vào:
limit = 5

Kết quả mong đợi:
expected = 3
Đầu vào:
long long limit = 5;

Kết quả mong đợi:
long long expected = 3;
Đầu vào:
long limit = 5;

Kết quả mong đợi:
long expected = 3;

Giải thích

1/3 lặp một chữ số, còn 1/2, 1/4 và 1/5 là hữu hạn, nên đáp án là 3.

Hướng tiếp cận

Hãy tự thử trước, sau đó mở từng gợi ý một.

Gợi ý 1

Mỗi chữ số mới của 1/d có được từ số dư nhân 10.

Gợi ý 2

Ghi nhớ bước mà mỗi số dư xuất hiện lần đầu.

Gợi ý 3

Nếu số dư bằng 0 thì số thập phân là hữu hạn; ngược lại, độ dài chu kỳ là khoảng cách giữa hai lần gặp cùng một số dư.

Độ phức tạp mong đợi

thời gian O(limit²), bộ nhớ phụ O(limit)

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.