{"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} x}$；\n* $\\displaystyle{\\sum_{x\\in S} x=\\min_{x\\in S} x+\\max_{x\\in S}x+{\\operatorname{mex}}(S)}$。\n\n**注： $\\bf{mex}$ 指集合中没有出现过的最小的自然数。**\n\n## Input\n\n**本题包含多组测试数据。**\n\n输入的第一行包含一个正整数 $T$，表示测试数据组数。\n\n对于每组测试数据，输入包含一行两个正整数 $n,k$。\n\n## Output\n\n对于每组测试数据，输出一行一个整数表示答案。\n\n[samples]\n\n## Background\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/s502kfip.png)\n\n## Note\n\n**【补充说明】**\n\n为了更好的让选手理解题面，给出若干合法/不合法集合例子：\n\n+ $\\{0,1,2,2\\}$。\n\n该集合是一个符合要求的集合，因为 $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$。\n\n+ $\\{3,5\\}$\n\n该集合不是一个符合要求的集合，因为虽然 $3+5=8,\\min\\{3,5\\}+\\max\\{3,5\\}+\\operatorname{mex}\\{3,5\\}=3+5+0=8$，但是 $3\\times 5\\not=\\min\\{3,5\\}$。\n\n+ $\\{1,9,1,9,8,1,0\\}$。\n\n该集合不是一个符合要求的集合，因为虽然 $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$。\n\n**【数据范围】**  \n\n对于 $100\\%$ 的数据，保证 $1\\le T\\le10^6$，$1\\le n,k\\le10^{18}$。\n\n|测试点编号|分值|$T\\le$|$k\\le$|$n$|\n|:-:|:-:|:-:|:-:|:-:|\n|$1$|$10$|$5$|$5$|$\\le5$|\n|$2$|$10$|$10^5$|$10^{18}$|$=1$|\n|$3$|$10$|$10^5$|$10^{18}$|$=2$|\n|$4$|$10$|$10^5$|$10^{18}$|$=3$|\n|$5$|$10$|$10^5$|$10^{18}$|$=4$|\n|$6$|$10$|$10^5$|$10^{18}$|$=5$|\n|$7$|$10$|$10^5$|$10$|$\\le10$|\n|$8$|$10$|$10^5$|$10^3$|$\\le10^3$|\n|$9$|$10$|$10^6$|$10^{18}$|$\\le10^{8}$|\n|$10$|$10$|$10^6$|$10^{18}$|$\\le10^{18}$|","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9034","tags":["数学","2023","洛谷原创","O2优化","枚举","洛谷月赛","分类讨论"],"sample_group":[["7\n1 4\n2 4\n5 3\n2 100\n3 8\n20 50\n499122178 4","1\n2\n0\n3\n5\n39\n998244353\n"]],"created_at":"2026-03-03 11:09:25"}}