No.1036 Make One With GCD 2
ningenMe
chocoruskProblem Statement
You are given a sequence $A$ consisting of $N$ elements. The $i$-th element ($1 \le i \le N$) is $A_i$. Consider the non-empty contiguous subsequences of this sequence.
Find the total number of contiguous subsequences of the sequence $A$ such that the greatest common divisor of all the elements contained in it is $1$.
Note that two contiguous subsequences are treated as different if they contain elements at different positions in the original sequence, even if the values of their elements are all the same.
Notes
The writer's solution got TLE on python3. It has been confirmed to get AC on pypy3.
[Added on 2020/04/26] Some test cases have been added since the contest, and the editorial has been revised.
Input
$N$
$A_{1}\ A_{2}\ \dots\ A_{N}$
All inputs are integers.
$1 \le N \le 500000$
$1 \le A_i \le 10^{18} (1 \le i \le N)$
Output
Print a newline at the end.
Sample
Sample 1
Input
3 1 2 3
Output
4
The 4 contiguous subsequences {1},{1,2},{2,3},{1,2,3} have a greatest common divisor of 1.
Sample 2
Input
4 1 1 1 1
Output
10
Note that contiguous subsequences are treated as different if they contain elements at different positions in the original sequence, even if the values of their elements are all the same.
Sample 3
Input
4 2 4 8 16
Output
0
No matter how a contiguous subsequence is chosen, none has a greatest common divisor of 1.
Sample 4
Input
10 801754 703742 332182 68016 914814 8470 937255 293192 313080 501971
Output
28
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。