[CERC2019] Be Geeks!

Luogu

IDLGP9607

Time2000ms

Memory128MB

DifficultyP6

2019线段树倍增ST 表ICPC笛卡尔树单调栈CERC

音乐乐队 Be Geeks! 的名字并非偶然，因为所有成员都是真正的数学怪才。除此之外，他们喜欢研究数列的各种性质。下面是他们感兴趣的一个例子： - 设 $A$ 是一个非空正整数序列，$A=(a_1, a_2, \dots, a_N)$。 - $G(i, j)=\gcd (a_i, a_{i+1}, \dots, a_j)$，其中 $1\le i\le j\le N$。 - $M(i, j)=\max (a_i, a_{i+1}, \dots, a_j)$，其中 $1\le i\le j\le N$。 - $P(i, j)=G(i, j)\times M(i, j)$，其中 $1\le i\le j\le N$。 - $F(A)=\sum P(i, j)[1\le i\le j\le N]$。给出一个序列 $A$，你需要求出 $F(A)\bmod 1\,000\,000\,007$ 的值。 ## Input 第一行包含一个整数 $N\ (1\le N\le 2\times 10^5)$，代表序列 $A$ 的长度。第二行包含 $N$ 个整数 $a_1, a_2, \dots, a_N\ (1\le a_i\le 10^9)$，代表序列 $A$。 ## Output 输出一个整数，代表 $F(A)\bmod 1\,000\,000\,007$ 的值。 [samples] ## Background **题目译自 [CERC 2019](https://contest.felk.cvut.cz/19cerc/solved.html) 「[Be Geeks!](https://contest.felk.cvut.cz/19cerc/solved/begeeks.pdf)」**

Samples

Input #1

4
1 2 3 4

Output #1

Input #2

5
2 4 6 12 3

Output #2

API Response (JSON)

{
  "problem": {
    "name": "[CERC2019] Be Geeks!",
    "description": {
      "content": "音乐乐队 Be Geeks! 的名字并非偶然，因为所有成员都是真正的数学怪才。除此之外，他们喜欢研究数列的各种性质。下面是他们感兴趣的一个例子： - 设 $A$ 是一个非空正整数序列，$A=(a_1, a_2, \\dots, a_N)$。 - $G(i, j)=\\gcd (a_i, a_{i+1}, \\dots, a_j)$，其中 $1\\le i\\le j\\le N$。 - $M(i, j)=\\m",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9607"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "音乐乐队 Be Geeks! 的名字并非偶然，因为所有成员都是真正的数学怪才。除此之外，他们喜欢研究数列的各种性质。下面是他们感兴趣的一个例子：\n- 设 $A$ 是一个非空正整数序列，$A=(a_1, a_2, \\dots, a_N)$。\n- $G(i, j)=\\gcd (a_i, a_{i+1}, \\dots, a_j)$，其中 $1\\le i\\le j\\le N$。\n- $M(i, j)=\\m...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments