Đề bài
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ụ
Đầ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.
Đầ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.