『XYGOI round1』三个数

Luogu
IDLGP9435
Time1000ms
Memory125MB
DifficultyP2
递推O2优化洛谷月赛
MX 有一个有 $(w-2)$ 个数的集合 $S=\{3,4,5,\cdots ,w\}$。要求构造一个只包含非负整数的集合(无重复元素),使得 $S$ 里面的任何一个数都能被这个集合里面大于等于 $3$ 个不同的数相加得到,求这个集合中至少包含多少个元素。 ## Input 本题包含多组测试数据。 第一行输入一个整数 $T$,表示数据组数。 接下来 $T$ 行每行输入一个整数 $w$。 ## Output 共 $T$ 行,每行输出一个整数 $n$,表示集合至少应该含有的元素个数。 [samples] ## Note #### 样例 1 说明: 集合元素可以为 $0,1,2,3$。 #### 数据范围: **本题采用捆绑测试。** 对于所有数据,保证 $1\le T \le 10^5$,$3\le w \le 10^{12}$。 | Subtask | $T$ | $w$ | 分值 | |:-:|:-:|:-:|:-:| |0|$=1$|$w\le 10$|5| |1|$1\le T\le 10^3$|$w\le 20$|10| |2|$1\le T\le 50$|$w\le 10^{3}$|25| |3|$1\le T\le 10^3$|$w\le 10^{5}$|30| |4|$1\le T\le 10^5$|$3\le w\le 10^{12}$|30|
Samples
Input #1
1
4
Output #1
4
Input #2
5
3
18
999
9999
9999999999
Output #2
3
6
12
15
35
API Response (JSON)
{
  "problem": {
    "name": "『XYGOI round1』三个数",
    "description": {
      "content": "MX 有一个有 $(w-2)$ 个数的集合 $S=\\{3,4,5,\\cdots ,w\\}$。要求构造一个只包含非负整数的集合(无重复元素),使得 $S$ 里面的任何一个数都能被这个集合里面大于等于 $3$ 个不同的数相加得到,求这个集合中至少包含多少个元素。",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 128000
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9435"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "MX 有一个有 $(w-2)$ 个数的集合 $S=\\{3,4,5,\\cdots ,w\\}$。要求构造一个只包含非负整数的集合(无重复元素),使得 $S$ 里面的任何一个数都能被这个集合里面大于等于 $3$ 个不同的数相加得到,求这个集合中至少包含多少个元素。\n\n## Input\n\n本题包含多组测试数据。\n\n第一行输入一个整数 $T$,表示数据组数。\n\n接下来 $T$ 行每行输入一个整数 $w$。\n...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments