Tổng dư
View as PDF
Submit solution
Points:
1400 (partial)
Time limit:
2.0s
Memory limit:
512M
Input:
stdin
Output:
stdout
Author:
Problem types
Cho dãy số a gồm n phần tử. Tính:
- \sum_{i=1}^{n-1} \sum^{n}_{j=i+1} |a_i mod a_j - a_j mod a_i|.
- Với mod là chia lấy dư, |x| là giá trị tuyệt đối của x.
Input, Output and Scoring
Input (bàn phím)
- Dòng đầu tiên gồm số nguyên n (n\le 10^5).
- Dòng tiếp theo gồm n số nguyên dương a_i (a_i\le 2\cdot 10^5).
- Các số trong dãy a đều phân biệt, nói cách khác với i\ne j thì a_i\ne a_j.
Output (màn hình)
- In ra một số nguyên duy nhất là kết quả của bài toán.
Scoring
- Subtask 1 (25\%): n\le 1000.
- Subtask 2 (25\%): a_i=i.
- Subtask 3 (50\%): không có giới hạn gì thêm.
Test
Input (bàn phím)
5
1 2 3 4 5
Output (màn hình)
14
Note
Gọi f(i,j) =|a_i mod a_j - a_j mod a_i|
- f(1,2) = 1
- f(1,3) = 1
- f(1,4) = 1
- f(1,5) = 1
- f(2,3) = 1
- f(2,4) = 2
- f(2,5) = 1
- f(3,4) = 2
- f(3,5) = 1
- f(4,5) = 3
=> Kết quả sẽ là 1+1+1+1+1+2+1+2+1+3=14.
Comments