VO 14 Bài 4 - Tổng ước chung lớn nhất

View as PDF

Submit solution

Points: 1.21 (partial)
Time limit: 4.5s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
VNOI Online 14 - Nguyễn Tấn Sỹ Nguyên
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Giáo sư Honest là một tay bịp bợm có hạng trong giới khoa học. Ngày hôm qua, hắn vừa tuyên bố rằng đã phát minh ra thuật toán tính ước chung lớn nhất của một dãy số có độ phức tạp ~\mathcal{O}\left(\frac{1}{N}\right)~, tức là input càng lớn thì thuật toán chạy càng nhanh.

Trong báo cáo khoa học của mình, Honest bày ra thí nghiệm như sau:

Cho một dãy số gồm ~N~ số nguyên dương. Honest tính tổng của các ước chung lớn nhất của tất cả các dãy con liên tiếp của dãy số trên (dãy con liên tiếp của một dãy số ~N~ phần tử được định nghĩa là dãy con chứa phần tử thứ ~L, L + 1, ..., R~ với ~1 \leq L \leq R \leq N)~.

Honest tuyên bố rằng hắn có thể thực hiện thao tác vừa rồi trong ~\mathcal{O}(N)~ bằng cách áp dụng thuật toán tính ước chung lớn nhất của một dãy số trên tất cả ~\frac{N * (N + 1)}{2}~, tức là ~\mathcal{O}(N^{2})~, dãy con liên tiếp của dãy số. Vì thế, thuật toán của hắn ta có độ phức tạp là ~\mathcal{O}\left(\frac{1}{N}\right)~.

"Không thể nào có chuyện như vậy!!!". Hội đồng khoa học của diễn đàn VNOI muốn lật tẩy trò lừa trẻ con của Honest. Tuy nhiên thì đầu tiên họ cần tìm ra cách để thực hiện lại thí nghiệm của Honest với tốc độ nhanh nhất có thể. Các bạn hãy giúp in ra số dư của kết quả thí nghiệm mà Honest đã tiến hành khi chia cho ~10^{9} + 7~ nhé.

Input

  • Dòng thứ nhất chứa số nguyên ~N~.
  • Dòng thứ hai chứa ~N~ số của dãy ~A~.

Output

  • Một số duy nhất là phần dư của kết quả tìm được khi chia cho ~10^{9} + 7~.

Giới hạn

  • Subtask ~1~ ~(15\%)~: ~1 \leq N \leq 100, 1 \leq A_{i} \leq 10^{12}~
  • Subtask ~2~ ~(15\%)~: ~1 \leq N \leq 5000, 1 \leq A_{i} \leq 10^{12}~
  • Subtask ~3~ ~(30\%)~: ~1 \leq N \leq 10^{5}, 1 \leq A_{i} \leq 200~
  • Subtask ~4~ ~(40\%)~: ~1 \leq N \leq 10^{5}, 1 \leq A_{i} \leq 10^{12}~
  • Thời gian chạy cho subtask ~1~ và ~2~ là ~1~s, subtask ~3~ và ~4~ là ~3~s.

Sample Input

4
3 6 5 8

Sample Output

30

Comments

Please read the guidelines before commenting.


There are no comments at the moment.