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

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:C CPP C++ 4.3.2 PAS-GPC PAS-FPC
Nguồn bài:VNOI Online 14 - Nguyễn Tấn Sỹ Nguyên

hide comments
2013-12-22 16:53:59 Ngô Huỳnh Ngọc Khánh♥(TN)♥
thật sự thì mình nghĩ người bày ra thí nghiệm này không phải là giáo sư Honest. Có ai suy nghĩ giống mình không :D?
2013-12-22 15:49:22 VOJ Team
X=Honest
2013-12-22 15:28:28 Nguyen Tien Trung Kien
Phía trên là "Giáo sư Honest", phía dưới là "X bày ra thí nghiệm như sau", vậy X và Honest là hai người hay một người? :v
2013-12-22 14:34:14 livw
1 pt thì UCLN của nó là chính nó, thế còn với dãy 3 6 4 thì UCLN là 1 à?
2013-12-22 14:26:06 Phạm Bá Thái
Kết quả phải là 13 chứ nhỉ? Dãy con có 1 phần tử thì có ước chung lớn nhất của 1 số à? Kết quả 34 thì có N*(N+1)/2 dãy con mất rồi!!!

Last edit: 2013-12-22 14:29:38
2013-12-22 14:16:08 livw
UCLN của đoạn 1-3 là bao nhiêu?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.