[入门赛 #11] 移植柳树 (Hard Version)

Luogu
IDLGP9213
Time1000ms
Memory512MB
DifficultyP2
2023Special JudgeO2优化语言月赛
假设总共有 $n$ 棵柳树,每一棵间隔都为 $x$。 现在他需要对这些树做一些操作,使得在「这 $n$ 棵树的起点不变」的同时,任意两棵树的间隔都为 $y$($y > x$)。 他被允许做的操作如下; - 移植树木:将一个位置的树木移到另一个位置上。 如果对「起点不变」这个概念有疑惑,可以参照「样例解释」中的图例。 显然操作是需要体力的,HG 想要让尽可能多的树维持原状。现在 HG 想知道,为了达成「任意两棵树的间隔都为 $y$」这个目标,他最多可以让多少棵树保持在原来的位置。 请你帮帮他吧! ## Input **本题单个测试点内含有多组测试数据。** 输入共 $T + 1$ 行。 第一行为一个整数 $T$,代表测试数据组数。 接下来 $T$ 行,每行三个整数 $n, x, y$,依次表示柳树的数量,未调整前每棵的间隔,想要达成的每棵的间隔。 ## Output 输出共 $T$ 行,每行一个整数,表示对于对应的输入数据,为了达成「任意两棵树的间隔都为 $y$」的目标, HG 最多可以让多少棵树保持在原来的位置。 [samples] ## Background **本题与 Easy Version 题意完全相同,不同的地方仅在于数据范围和单个测试点内含有的测试组数量。** HG 在上学的路上无聊的走着,看着这马路边的一排柳树,他的脑子里突然冒出了个奇怪的问题…… ## Note ### 样例 1 解释 ![](https://cdn.luogu.com.cn/upload/image_hosting/6uguqush.png) 图中的方块代表树。第一行为调整前,第二行为调整后的情况。标出的三个绿色的方块是不需要移动的树,除此之外其他树都需要移动。 ### 数据规模与约定 对于 $100\%$ 的数据,保证 $1 \leq T \leq 10 ^ 5$,$1 \leq n \leq 10 ^ {18}$,$1 \leq x < y \leq 10 ^ 9$。
Samples
Input #1
1
8 2 3
Output #1
3
API Response (JSON)
{
  "problem": {
    "name": "[入门赛 #11] 移植柳树 (Hard Version)",
    "description": {
      "content": "假设总共有 $n$ 棵柳树,每一棵间隔都为 $x$。 现在他需要对这些树做一些操作,使得在「这 $n$ 棵树的起点不变」的同时,任意两棵树的间隔都为 $y$($y > x$)。 他被允许做的操作如下; - 移植树木:将一个位置的树木移到另一个位置上。 如果对「起点不变」这个概念有疑惑,可以参照「样例解释」中的图例。 显然操作是需要体力的,HG 想要让尽可能多的树维持原状。现在 HG 想",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P2"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9213"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "假设总共有 $n$ 棵柳树,每一棵间隔都为 $x$。\n\n现在他需要对这些树做一些操作,使得在「这 $n$ 棵树的起点不变」的同时,任意两棵树的间隔都为 $y$($y > x$)。\n\n他被允许做的操作如下;\n\n- 移植树木:将一个位置的树木移到另一个位置上。\n\n如果对「起点不变」这个概念有疑惑,可以参照「样例解释」中的图例。\n\n显然操作是需要体力的,HG 想要让尽可能多的树维持原状。现在 HG 想知...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments