[NICA #2] 回来吧我的小波

Luogu
IDLGB3832
Time1000ms
Memory512MB
DifficultyP3
模拟数学O2优化枚举
给定一个仅包含数字 $1,2,3,4,5,6,7,8,9$ 的数字串 $s$,你要选择两个不交区间 $[l_1,r_1],[l_2,r_2](1\le l_1\le r_1<l_2\le r_2\le |s|)$,设 $[l_1,r_1]$ 区间串取出来的数字为 $x$,$[l_2,r_2]$ 区间串取出来的数字为 $y$,要求 $x|y$。如果存在这样两个不交区间,那么我们称数字串 $s$ 是好的。(这里的 $|$ 表示整除,你可以理解为 $x$ 为 $y$ 的一个因数) 现在给定一个仅包含数字 $1,2,3,4,5,6,7,8,9$ 的数字串 $S$,询问它有多少个子串是好的。(这里的子串**不要求**是本质不同的) ## Input 输入仅一行一个仅包含 $1,2,3,4,5,6,7,8,9$ 的数字串 $S$。 ## Output 输出一个正整数,表示好的子串数量。 [samples] ## Background 小波我错了,你快回来吧! ## Note #### 样例1解释 只有一个好串 `327`,你可以选择两个不交区间 $[1,1],[2,3]$,取出来的数字分别是 $3$ 和 $27$,显然 $3$ 是 $27$ 的一个因数,所以这个串是好串。 其他子串 `3`,`2`,`7`,`32`,`27` 都不是好的,因为不存在这样的两个不交区间。 #### 样例2解释 共有 $12$ 个好串,分别为 `114514`、`11451`、`1145`、`114`、`11`、`14514`、`1451`、`145`、`14`、`4514`、`514`、`14`。(注意到里面有两个 `14`,但是由于它们位置不同,我们还是认为这是两个不同的子串) #### 数据范围 对于所有数据,保证 $2\le |S|\le 10^6$。
Samples
Input #1
327
Output #1
1
Input #2
114514
Output #2
12
API Response (JSON)
{
  "problem": {
    "name": "[NICA #2] 回来吧我的小波",
    "description": {
      "content": "给定一个仅包含数字 $1,2,3,4,5,6,7,8,9$ 的数字串 $s$,你要选择两个不交区间 $[l_1,r_1],[l_2,r_2](1\\le l_1\\le r_1<l_2\\le r_2\\le |s|)$,设 $[l_1,r_1]$ 区间串取出来的数字为 $x$,$[l_2,r_2]$ 区间串取出来的数字为 $y$,要求 $x|y$。如果存在这样两个不交区间,那么我们称数字串 $s$ 是好",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB3832"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一个仅包含数字 $1,2,3,4,5,6,7,8,9$ 的数字串 $s$,你要选择两个不交区间 $[l_1,r_1],[l_2,r_2](1\\le l_1\\le r_1<l_2\\le r_2\\le |s|)$,设 $[l_1,r_1]$ 区间串取出来的数字为 $x$,$[l_2,r_2]$ 区间串取出来的数字为 $y$,要求 $x|y$。如果存在这样两个不交区间,那么我们称数字串 $s$ 是好...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments