实力派

Luogu

IDLGP10269

Time1000ms

Memory512MB

DifficultyP6

数论素数判断,质数,筛法最大公约数 gcd莫比乌斯反演

来自全国各地的 $n$ 位 OIer 组成了一个名为“实力派”的团队，每个人有一个实力值 $a_i$。共有 $m$ 场比赛向他们发送了参赛邀请，其中第 $i$ 场比赛要求 $k_i$ 个人组成一个队伍参加。为了决定他们是否应该参加某场比赛，他们想出了如下两个衡量实力的数据： - 定义 $x$ 阶最低实力表示从这 $n$ 个人中选出 $x$ 个人，使得这 $x$ 个人实力值的 $\gcd=1$ 的方案数； - 定义 $x$ 阶最高实力表示从这 $n$ 个人中选出 $x$ 个人，所有方案的 $x$ 个人的 $\gcd$ 之和。请你对于每场比赛，告诉他们他们在这场比赛中的 $k_i$ 阶最低实力和最高实力。对了，为了不让别人听懂，你需要将答案对一个秘密模数 $p$ 取模。 ## Input 第一行三个整数 $n,m,p$，分别表示团队人数，比赛场数及秘密模数；第二行 $n$ 个整数，第 $i$ 个整数表示第 $i$ 个人的实力值 $a_i$。接下来 $m$ 行，第 $i$ 行一个整数 $k_i$，表示第 $i$ 场比赛的要求参赛人数。 ## Output 输出共 $m$ 行，第 $i$ 行两个整数 $min_i,max_i$，分别表示他们在第 $i$ 场比赛中的最低实力和最高实力，答案对 $p$ 取模。 [samples] ## Background ![](https://cdn.luogu.com.cn/upload/image_hosting/z8ednvb2.png) ## Note **样例** $\mathbf{1}$ **解释** 第一场比赛要求选出 $2$ 人参加，仅有 $(8,15)$ 一种方案的 $\gcd=1$，因此最低实力为 $1$；所有方案的 $\gcd$ 之和为 $19$，因此最高实力为 $19$；第二场比赛要求选出 $3$ 人参加，有 $(8,15,12)$ 和 $(8,15,6)$ 两种 $\gcd=1$ 的方案，因此最低实力为 $2$；所有方案的 $\gcd$ 之和为 $7$，因此最高实力为 $7$。 **数据范围** 对于所有数据，$1\leq n,m,k_i\leq 2\times 10^5$，$1\leq a_i\leq 10^6$，$10^7\leq p\leq 10^9$，$p\in \mathbb{P}$。本题共 $30$ 个测试点，**采用捆绑测试**，子任务及数据点分配如下： | 子任务编号 | 数据点编号 | 特殊性质 | 分值 | 时限 | | :-: | :-: | :-: | :-: | :-: | | $0$ | $1\sim 4$ | $n\leq 20$ | $10$ | $1s$ | | $1$ | $5\sim 8$ | $n,a_i\leq 300$ | $10$ | $1s$ | | $2$ | $9\sim 12$ | $k_i\leq 2$ | $20$ | $1.5s$ | | $3$ | $13\sim 16$ | $a_i\leq 3$ | $10$ | $1s$ | | $4$ | $17\sim 22$ | $a_i\leq 10^5$ | $20$ | $1s$ | | $5$ | $23\sim 30$ | 无特殊性质 | $30$ | $1.5s$ | **提示** $\mathbb{P}$ 表示全体质数集合，$\gcd$ 表示最大公因数。

Samples

Input #1

4 4 998244353
8 15 12 6
2
3
4
5

Output #1

Input #2

6 4 19260817
11 45 14 19 19 810
2
1
2
2

Output #2

Input #3

8 3 19491001
3 2 2 3 1 2 1 2
5
3
4

Output #3

56 56
52 60
69 71

API Response (JSON)

{
  "problem": {
    "name": "实力派",
    "description": {
      "content": "来自全国各地的 $n$ 位 OIer 组成了一个名为“实力派”的团队，每个人有一个实力值 $a_i$。共有 $m$ 场比赛向他们发送了参赛邀请，其中第 $i$ 场比赛要求 $k_i$ 个人组成一个队伍参加。为了决定他们是否应该参加某场比赛，他们想出了如下两个衡量实力的数据： - 定义 $x$ 阶最低实力表示从这 $n$ 个人中选出 $x$ 个人，使得这 $x$ 个人实力值的 $\\gcd=1$ 的",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P6"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10269"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "来自全国各地的 $n$ 位 OIer 组成了一个名为“实力派”的团队，每个人有一个实力值 $a_i$。共有 $m$ 场比赛向他们发送了参赛邀请，其中第 $i$ 场比赛要求 $k_i$ 个人组成一个队伍参加。为了决定他们是否应该参加某场比赛，他们想出了如下两个衡量实力的数据：\n\n- 定义 $x$ 阶最低实力表示从这 $n$ 个人中选出 $x$ 个人，使得这 $x$ 个人实力值的 $\\gcd=1$ 的...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments