Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

VOGCDSUM - Tổng ước chung lớn nhất

Hiện tại, bài tập này đã có trên online judge chính thức của VNOI, bạn có thể truy cập ở đây: https://oj.vnoi.info/problem/vogcdsum


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 O(1 / N), 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 ≤ L ≤ R ≤ N).

Honest tuyên bố rằng hắn có thể thực hiện thao tác vừa rồi trong 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ả N * (N + 1) / 2, tức là O(N2), 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à O(1 / N). 

"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 109 + 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 109 + 7.

Giới hạn

  • Subtask 1 (15%): 1 ≤ N ≤ 100, 1 ≤ Ai ≤ 1012
  • Subtask 2 (15%): 1 ≤ N ≤ 5000, 1 ≤ Ai ≤ 1012
  • Subtask 3 (30%): 1 ≤ N ≤ 105, 1 ≤ Ai ≤ 200
  • Subtask 4 (40%): 1 ≤ N ≤ 105, 1 ≤ Ai ≤ 1012
  • Thời gian chạy cho subtask 1 và 2 là 1s, subtask 3 và 4 là 3s.

Chấm điểm

  • Trong thời gian thi, bài của bạn sẽ chỉ được chấm với duy nhất 1 test có trong đề bài.

Ví dụ

Input:

4
3 6 4 8

Output:

34


Được gửi lên bởi:VOJ Team
Ngày:2013-12-17
Thời gian chạy:1s-3s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:VNOI Online 14 - Nguyễn Tấn Sỹ Nguyên

hide comments
2019-07-20 09:35:51
ez from le trong tam
2018-09-14 16:57:49
cayyyyy
2018-08-25 03:33:49
code + solution :)) https://bit.ly/2eGhgab
2017-05-03 05:15:22
manhj beos loif mowx
2017-05-03 05:14:59
manhj beos yeeu xuaan
2016-12-06 15:22:25
gg ez http://www.liink.pw/4Aq9
2016-12-05 09:45:01
..
2016-12-05 08:40:00
trâu cx 100
2016-11-30 04:54:09
.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.