Số Mersenne (HSG9 NB 2023)
Xem PDF
Nộp bài
Điểm:
1000 (thành phần)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
mersen.inp
Output:
mersen.out
Tác giả:
Dạng bài
Một số nguyên tố được gọi là số Mersenne nếu nó có thể biểu diễn dưới dạng 2^k-1 trong đó k cũng là 1 số nguyên tố.
Yêu cầu: Cho số tự nhiên n. Tìm số Mersenne lớn nhất nhưng nhỏ hơn n.
Input, Output và Subtasks
Input: (mersen.inp)
- Ghi số nguyên n (3<n\le 10^{10})
Output: (mersen.out)
- Ghi số Mersenne lớn nhất nhưng nhỏ hơn n tìm được
Subtasks
- Subtask 1 (40\%): n\le 10^5
- Subtask 2 (40\%): n\le 10^9
- Subtask 3 (20\%): Không có ràng buộc gì thêm
Sample 1
Input (mersen.inp)
4
Output (mersen.out)
3
Note
Ta có: 3=2^2-1 và 3,2 đều là số nguyên tố. Do đó, 3 là số Mersenne lớn nhất nhưng nhỏ hơn 4
Sample 2
Input (mersen.inp)
9
Output (mersen.out)
7
Note
Ta có: 7=2^3-1 và 7,3 đều là số nguyên tố. Do đó, 7 là số Mersenne lớn nhất nhưng nhỏ hơn 9
Bình luận