Vẻ đẹp của số dư
Xem PDF
Điểm:
300 (p)
Thời gian:
2.0s
Bộ nhớ:
977M
Input:
bàn phím
Output:
màn hình
Hường là một cô bạn có niềm đam mê Toán học rất mãnh liệt. Hôm nay trong tiết học Toán thầy có dạy về số dư. Hường cảm thấy rất phấn khích với tiết học này, thậm chí sau đó còn mua rất nhiều sách đọc về “vẻ đẹp của số dư”. Cường là bạn thân của Hường nhưng cậu lại yêu môn Tin học hơn là Toán. Thấy bạn mình say mê với số dư, Cường có đố Hường một bài toán như sau:
Cho một dãy số \(A\) gồm \(N\) số nguyên dương đôi một khác nhau \(A_1, A_2, \dots A_N\), hãy tìm hai chỉ số \(i\) và \(j\) (\(A_i<A_j\)) sao cho biểu thức \(A_j \mod A_i\) đạt giá trị lớn nhất.
Hường loay hoay mãi vẫn không giải được bài toán. Các bạn hãy giúp Hường nhé!!!
Input
- Dòng đầu tiên chứa 1 số nguyên dương \(N\) \((N \leq 10^5)\) là độ dài của dãy số.
- Dòng tiếp theo chứa \(N\) số nguyên dương \(A_1, A_2, \dots A_N\) \((A_i \leq 10^6)\).
Output
- In ra giá trị lớn nhất của \(A_j \mod A_i\) \((i<j)\).
Scoring
- Subtask \(1\) (\(30\%\) số điểm): \(N \leq 10^3\).
- Subtask \(2\) (\(30\%\) số điểm): \(N \leq 10^4\)
- Subtask \(3\) (\(40\%\) số điểm): \(N \leq 10^5, A_i \leq 10^6\)
Example
Test 1
Input
4
2 3 4 5 Output
2
Bình luận
=)) Chặt nhị phân ?
11
1279 7555 1838 7711 8903 1411 4105 7488 7445 2203 483
test 1 ra 7488 chứ nhỉ ?
7488 mod 7555 = 7488 (j = 8, i = 2)
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.