「KDOI-04」Again Counting Set

Luogu

IDLGP9034

Time2000ms

Memory512MB

DifficultyP4

数学2023洛谷原创O2优化枚举洛谷月赛分类讨论

小 S 不喜欢集合，不喜欢自然数，不喜欢求和，不喜欢求积，不喜欢最小值，不喜欢最大值，不喜欢 $\operatorname{mex}$，所以有了这题。给出 $n,k$，求有多少个可重**整数**集合 $S$ 满足： * $|S|=k$； * 对于任意 $x\in S$，$0\le x\le n$； * $\displaystyle{\prod_{x\in S} x=\min_{x\in S} x}$； * $\displaystyle{\sum_{x\in S} x=\min_{x\in S} x+\max_{x\in S}x+{\operatorname{mex}}(S)}$。 **注： $\bf{mex}$ 指集合中没有出现过的最小的自然数。** ## Input **本题包含多组测试数据。** 输入的第一行包含一个正整数 $T$，表示测试数据组数。对于每组测试数据，输入包含一行两个正整数 $n,k$。 ## Output 对于每组测试数据，输出一行一个整数表示答案。 [samples] ## Background ![](https://cdn.luogu.com.cn/upload/image_hosting/s502kfip.png) ## Note **【补充说明】** 为了更好的让选手理解题面，给出若干合法/不合法集合例子： + $\{0,1,2,2\}$。该集合是一个符合要求的集合，因为 $0\times 1\times 2\times 2=0=\min\{0,1,2,2\}$，$0+1+2+2=5,\min\{0,1,2,2\}+\max\{0,1,2,2\}+\operatorname{mex}\{0,1,2,2\}=0+2+3=5$。 + $\{3,5\}$ 该集合不是一个符合要求的集合，因为虽然 $3+5=8,\min\{3,5\}+\max\{3,5\}+\operatorname{mex}\{3,5\}=3+5+0=8$，但是 $3\times 5\not=\min\{3,5\}$。 + $\{1,9,1,9,8,1,0\}$。该集合不是一个符合要求的集合，因为虽然 $1\times 9\times 1\times 9\times 8\times 1\times 0=0=\min\{1,9,1,9,8,1,0\}$，但是其和为 $29$ 而并非 $\min+\max+\operatorname{mex}=0+9+2=11$。 **【数据范围】** 对于 $100\%$ 的数据，保证 $1\le T\le10^6$，$1\le n,k\le10^{18}$。 |测试点编号|分值|$T\le$|$k\le$|$n$| |:-:|:-:|:-:|:-:|:-:| |$1$|$10$|$5$|$5$|$\le5$| |$2$|$10$|$10^5$|$10^{18}$|$=1$| |$3$|$10$|$10^5$|$10^{18}$|$=2$| |$4$|$10$|$10^5$|$10^{18}$|$=3$| |$5$|$10$|$10^5$|$10^{18}$|$=4$| |$6$|$10$|$10^5$|$10^{18}$|$=5$| |$7$|$10$|$10^5$|$10$|$\le10$| |$8$|$10$|$10^5$|$10^3$|$\le10^3$| |$9$|$10$|$10^6$|$10^{18}$|$\le10^{8}$| |$10$|$10$|$10^6$|$10^{18}$|$\le10^{18}$|

Samples

Input #1

7
1 4
2 4
5 3
2 100
3 8
20 50
499122178 4

Output #1

API Response (JSON)

{
  "problem": {
    "name": "「KDOI-04」Again Counting Set",
    "description": {
      "content": "小 S 不喜欢集合，不喜欢自然数，不喜欢求和，不喜欢求积，不喜欢最小值，不喜欢最大值，不喜欢 $\\operatorname{mex}$，所以有了这题。 给出 $n,k$，求有多少个可重**整数**集合 $S$ 满足： * $|S|=k$； * 对于任意 $x\\in S$，$0\\le x\\le n$； * $\\displaystyle{\\prod_{x\\in S} x=\\min_{x\\in S}",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9034"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 S 不喜欢集合，不喜欢自然数，不喜欢求和，不喜欢求积，不喜欢最小值，不喜欢最大值，不喜欢 $\\operatorname{mex}$，所以有了这题。\n\n给出 $n,k$，求有多少个可重**整数**集合 $S$ 满足：\n\n* $|S|=k$；\n* 对于任意 $x\\in S$，$0\\le x\\le n$；\n* $\\displaystyle{\\prod_{x\\in S} x=\\min_{x\\in S}...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments