RoAlgo Contest #4 (avansati) | gadfadar5

This was the problem page during the contest. Access the current page here.
Time limit: 0.75s Memory limit: 256MB Input: Output:

Dude, you still have two lives

Don loves correctly parenthesized strings, your friend Raul loves sequences, and you love number theory. Don asked you to write a problem that meets the quality of the RoAlgo contest problems and to give a solution to this problem. You decided to combine number theory, correctly parenthesized strings, and sequences into a single problem.

A string is called correctly parenthesized if and only if you can insert the characters ++ and 11 such that the resulting string represents a correct mathematical expression. For example, (())(()) and ()(())()(()) are correctly parenthesized strings because (1+(1+1))(1+(1+1)) and (1+1)+(1+(1+1))(1+1)+(1+(1+1)) are correct mathematical expressions, but (()(() and ())(()())(() are not correctly parenthesized strings.

Task

You are given the number nn and a string SS of characters belonging to the set {(,)}\{ \texttt{(}, \texttt{)} \} of length nn.

Find i=1nj=ingcd(i,j)rbs(i,j)\displaystyle{\sum_{i=1}^{n} \sum_{j=i}^{n} gcd(i, j) \cdot rbs(i, j)}

Input data

The first line will contain a single natural number representing the number nn.

The second line contains a string of nn characters representing the string SS.

Output data

Output a single natural number representing the answer to the task.

Constraints and clarifications

  • 1n200 0001 \leq n \leq 200 \ 000
  • gcd(i,j)gcd(i, j) is the greatest common divisor of the numbers ii and jj.
  • rbs(i,j)rbs(i, j) is 11 if the subsequence si si+1  sjs_i \ s_{i+1} \ \dots \ s_j is correctly parenthesized, otherwise it is 00
# Points Constraints
1 6 1n3001 \leq n \leq 300
2 11 300<n3 000300 < n \leq 3 \ 000
3 65 3 000<n50 0003 \ 000 < n \leq 50 \ 000
4 18 No other constraints

Example

stdin

10
()()((()))

stdout

14

Explanation

The subsequences with gcd(i,j)=1gcd(i, j) = 1 are:

  1. (1,2)(1, 2)
  2. (1,4)(1, 4)
  3. (1,10)(1, 10)
  4. (3,4)(3, 4)
  5. (3,10)(3, 10)
  6. (7,8)(7, 8)

The subsequence with gcd(i,j)=3gcd(i, j) = 3 is:

  1. (6,9)(6, 9)

The subsequence with gcd(i,j)=5gcd(i, j) = 5 is:

  1. (5,10)(5, 10)

61+13+15=146 \cdot 1 + 1 \cdot 3 + 1 \cdot 5 = 14

Therefore, the answer is 1414.

Log in or sign up to be able to send submissions!