『XYGOI round1』好多数

Luogu
IDLGP9438
Time2000ms
Memory512MB
DifficultyP5
O2优化洛谷月赛
小 X 想到了另外一个东西,也是严重右偏的。 首先,他写下一个数字 $n$。 接着,对于所有 $n$ 的因数 $x\notin\{1,n\}$,让 $x$ 从小到大的成为 $n$ 的儿子节点。 递归的建这棵树,这棵树就建成了。小 X 把这棵树称为一个“$n$ 号数学树”。小 X 想知道,给定 $q$ 个正整数 $x$,它在 $n$ 号数学树出现了几次。 因为 $n$ 很大,他只能告诉你 $n$ 的质因数分解。 答案对 $998244353$ 取模。 ## Input 第一行若干对整数 $(a_i,b_i)$,表示 $n=\prod a_i^{b_i}$,以 `0 0` 结尾。题目保证,$a_i$ 是质数,$b_i\in N^*$。 第二行一个整数,表示 $q$,含义如题面所示。 第三行 $q$ 个整数,代表这组数据的 $q$ 次询问。 ## Output 输出一行 $q$ 个整数,表示每个询问的答案对 $998244353$ 取模的结果。 [samples] ## Background 小 X 在和小 L 一起玩。他们走到了公园,发现了一棵长得很奇怪的参天大树。这棵树,按照 OIer 们的习惯,它有一个明显特征,那就是**严重右偏**。 ## Note 样例解释:前两组数据均为 $24$ 号数学树。这棵树绘制以后如下: ![](https://cdn.luogu.com.cn/upload/image_hosting/ejrhdnv3.png) 其中,$2$ 出现了 $8$ 次,$3$ 出现了 $4$ 次,$5,7$ 则没有出现过。 对于第三组数据,你需要注意 $343$ 在 $343$ 号数学树的树根出现了一次,$1$ 不会在数学树中出现。 | Subtask | $n$ | $q$ | 保证 $n$ 是质数的幂 | 分值 | |:-:|:-:|:-:|:-:|:-:| |0|$\le 10^3$|$\le 20$|Yes|10| |1|$\le 10^6$|$\le 20$|No|10| |2|$\sum b_i\le5000$|$\le 20$|Yes|40| |3|$\sum b_i\le5000$|$\le 20$|No|40| 对于 $100\%$ 的数据,$1\le b_i \le 5000$,$\sum b_i\le5000$,$2\le a_i\le 10^9$,$1\le x\le 10^{18}$。
Samples
Input #1
2 3 3 1 0 0
1
2
Output #1
8
Input #2
2 3 3 1 0 0
3
3 5 7
Output #2
4 0 0
Input #3
7 3 0 0
3
49 1 343
Output #3
1 0 1
API Response (JSON)
{
  "problem": {
    "name": "『XYGOI round1』好多数",
    "description": {
      "content": "小 X 想到了另外一个东西,也是严重右偏的。 首先,他写下一个数字 $n$。   接着,对于所有 $n$ 的因数 $x\\notin\\{1,n\\}$,让 $x$ 从小到大的成为 $n$ 的儿子节点。  递归的建这棵树,这棵树就建成了。小 X 把这棵树称为一个“$n$ 号数学树”。小 X 想知道,给定 $q$ 个正整数 $x$,它在 $n$ 号数学树出现了几次。   因为 $n$ 很大,他只能",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P5"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP9438"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "小 X 想到了另外一个东西,也是严重右偏的。\n\n首先,他写下一个数字 $n$。  \n\n接着,对于所有 $n$ 的因数 $x\\notin\\{1,n\\}$,让 $x$ 从小到大的成为 $n$ 的儿子节点。 \n\n递归的建这棵树,这棵树就建成了。小 X 把这棵树称为一个“$n$ 号数学树”。小 X 想知道,给定 $q$ 个正整数 $x$,它在 $n$ 号数学树出现了几次。  \n\n因为 $n$ 很大,他只能...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments