GCD - MarisaOJ: Marisa Online Judge

GCD

Time limit: 750 ms
Memory limit: 256 MB
Given an array $A$ of $n$ integers, calculate: $$ \sum_{i=1}^{n} \sum_{j=i}^{n} \text{gcd}(A_i, A_{i+1},...,A_j) $$ ### Input - The first line contains an integer $n$. - The next line contains $n$ integer $A_i$. ### Output - Print the answer modulo $10^9+7$. ### Constraints - $1 \le n \le 10^5$. - $1 \le A_i \le 10^9$. ### Example Input: ``` 3 2 4 3 ``` Output: ``` 13 ```
Topic
Math
Binary search
Data structure
Rating 1700
Solution (1) Solution