[NICA #1] 乘只因

Luogu

IDLGB3801

Time2000ms

Memory128MB

DifficultyP3

数论O2优化素数判断,质数,筛法Stirling 数

给定 $n,k$，请统计有多少个长度为 $k$ 的序列 $[a_1,a_2,\dots,a_k]$ 满足： - $a_1\times a_2\times a_3\times \dots\times a_k=n$。 - $1<a_1\leq a_2\leq a_3\leq \dots\leq a_k$。 - 这 $k$ 个数的最小公倍数等于 $n$。 ## Input 本题多测，共 $T$ 组数据。第一行一个正整数 $T$，表示数据组数。对于每组数据，包含一行两个正整数 $n, k$。 ## Output 共 $T$ 行。每行一个数，第 $i$ 行表示第 $i$ 组数据的答案。 [samples] ## Background 咯咯咯（只因叫）。 ## Note #### 【样例解释】 - 只能拆分为 $2\times 5$。 - $2$ 和 $5$ 的最小公倍数为 $10$。 #### 【数据范围】对于 $100\%$ 的数据，满足 $n,k\leq 10^7$，$T\leq 10^5$。

Samples

Input #1

1
10 2

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[NICA #1] 乘只因",
    "description": {
      "content": " 给定 $n,k$，请统计有多少个长度为 $k$ 的序列 $[a_1,a_2,\\dots,a_k]$ 满足： - $a_1\\times a_2\\times a_3\\times \\dots\\times a_k=n$。 - $1<a_1\\leq a_2\\leq a_3\\leq \\dots\\leq a_k$。 - 这 $k$ 个数的最小公倍数等于 $n$。 ",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P3"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGB3801"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定 $n,k$，请统计有多少个长度为 $k$ 的序列 $[a_1,a_2,\\dots,a_k]$ 满足：\n\n- $a_1\\times a_2\\times a_3\\times \\dots\\times a_k=n$。\n- $1<a_1\\leq a_2\\leq a_3\\leq \\dots\\leq a_k$。\n- 这 $k$ 个数的最小公倍数等于 $n$。\n\n## Input\n\n本题多测，共 $T$ 组...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments