309686: CF1718F. Burenka, an Array and Queries
Memory Limit:256 MB
Time Limit:3 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
Burenka, an Array and Queries
题意翻译
#### 题目描述 Eugene 给 Burenka 送上了他的生日礼物——一个长度为 $ n $ 的数组 $ a $ ,其中包含从 $ 1 $ 到 $ m $ 的整数。 Burenka 知道 Eugene 非常喜欢互质的两个整数(互质:指整数 $ x $ 和 $ y $ 的最大公约数为 $1$),所以她想问 Eugene $ q $ 关于礼物的问题。 每次 Burenka 都会选择数组 $a$ 的一个子段$ a_l, a_{l + 1}, \ldots, a_r $,并计算这些数字的乘积 $ p = a_l \cdot a_{l + 1} \cdot ... \cdot a_r $ 。然后她会要求 Eugene 计算在 $1 $ 和 $C$ 之间与 $p$ 互质的整数个数。 请帮助 Eugene 回答所有问题。 #### 输入格式 在输入的第一行有四个整数 $ n $ , $ m $ , $ C $ , $ q $ ( $ 1 \leq n, q \leq 10^5 $ , $ 1 \leq m \leq 2\cdot 10^4 $ , $ 1 \leq C \leq 10^5 $ ) —— 数组 $ a $ 的长度、$ a_{i} $ 的最大可能值、$ C $ 的值和查询次数. 第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_{i} \leq m $ ), 指数组 $ a $ 。 在接下来的 $ q $ 行中每一行代表一次查询。每个查询由两个整数 $ l $ 和 $ r $ ( $ 1 \leq l \leq r \leq n $ ) 组成。 #### 输出格式 对于每个询问,输出一个整数 —— Burenka 查询的答案。 #### 提示 以下是样例的解释: 1. 在第一个查询中,乘积等于 $1$,与 $1,2,3,4,5$ 互质。 2. 在第二个查询中,乘积等于 $12$,它与 $1$ 和 $5$ 互质。 3. 在第三个查询中,乘积等于 $10$,它与 $1$ 和 $3$ 互质。题目描述
Eugene got Burenka an array $ a $ of length $ n $ of integers from $ 1 $ to $ m $ for her birthday. Burenka knows that Eugene really likes coprime integers (integers $ x $ and $ y $ such that they have only one common factor (equal to $ 1 $ )) so she wants to to ask Eugene $ q $ questions about the present. Each time Burenka will choose a subsegment $ a_l, a_{l + 1}, \ldots, a_r $ of array $ a $ , and compute the product of these numbers $ p = a_l \cdot a_{l + 1} \cdot \ldots \cdot a_r $ . Then she will ask Eugene to count the number of integers between $ 1 $ and $ C $ inclusive which are coprime with $ p $ . Help Eugene answer all the questions!输入输出格式
输入格式
In the first line of input there are four integers $ n $ , $ m $ , $ C $ , $ q $ ( $ 1 \leq n, q \leq 10^5 $ , $ 1 \leq m \leq 2\cdot 10^4 $ , $ 1 \leq C \leq 10^5 $ ) — the length of the array $ a $ , the maximum possible value of $ a_{i} $ , the value $ C $ , and the number of queries. The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_{i} \leq m $ ) — the array $ a $ . In the next $ q $ lines the queries are given. Each query consists of two integers $ l $ and $ r $ ( $ 1 \leq l \leq r \leq n $ ).
输出格式
Print $ q $ integers — the answers to Burenka's queries.
输入输出样例
输入样例 #1
5 5 5 3
1 2 3 2 5
1 1
2 4
4 5
输出样例 #1
5
2
2
说明
Here's an explanation for the example: 1. in the first query, the product is equal to $ 1 $ , which is coprime with $ 1,2,3,4,5 $ . 2. in the second query, the product is equal to $ 12 $ , which is coprime with $ 1 $ and $ 5 $ . 3. in the third query, the product is equal to $ 10 $ , which is coprime with $ 1 $ and $ 3 $ .Input
题意翻译
#### 题目描述 Eugene 给 Burenka 送上了他的生日礼物——一个长度为 $ n $ 的数组 $ a $ ,其中包含从 $ 1 $ 到 $ m $ 的整数。 Burenka 知道 Eugene 非常喜欢互质的两个整数(互质:指整数 $ x $ 和 $ y $ 的最大公约数为 $1$),所以她想问 Eugene $ q $ 关于礼物的问题。 每次 Burenka 都会选择数组 $a$ 的一个子段$ a_l, a_{l + 1}, \ldots, a_r $,并计算这些数字的乘积 $ p = a_l \cdot a_{l + 1} \cdot ... \cdot a_r $ 。然后她会要求 Eugene 计算在 $1 $ 和 $C$ 之间与 $p$ 互质的整数个数。 请帮助 Eugene 回答所有问题。 #### 输入格式 在输入的第一行有四个整数 $ n $ , $ m $ , $ C $ , $ q $ ( $ 1 \leq n, q \leq 10^5 $ , $ 1 \leq m \leq 2\cdot 10^4 $ , $ 1 \leq C \leq 10^5 $ ) —— 数组 $ a $ 的长度、$ a_{i} $ 的最大可能值、$ C $ 的值和查询次数. 第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_{i} \leq m $ ), 指数组 $ a $ 。 在接下来的 $ q $ 行中每一行代表一次查询。每个查询由两个整数 $ l $ 和 $ r $ ( $ 1 \leq l \leq r \leq n $ ) 组成。 #### 输出格式 对于每个询问,输出一个整数 —— Burenka 查询的答案。 #### 提示 以下是样例的解释: 1. 在第一个查询中,乘积等于 $1$,与 $1,2,3,4,5$ 互质。 2. 在第二个查询中,乘积等于 $12$,它与 $1$ 和 $5$ 互质。 3. 在第三个查询中,乘积等于 $10$,它与 $1$ 和 $3$ 互质。Output
**题意翻译**
#### 题目描述
Eugene 给 Burenka 送上了他的生日礼物——一个长度为 $ n $ 的数组 $ a $ ,其中包含从 $ 1 $ 到 $ m $ 的整数。 Burenka 知道 Eugene 非常喜欢互质的两个整数(互质:指整数 $ x $ 和 $ y $ 的最大公约数为 $1$),所以她想问 Eugene $ q $ 关于礼物的问题。
每次 Burenka 都会选择数组 $a$ 的一个子段$ a_l, a_{l + 1}, \ldots, a_r $,并计算这些数字的乘积 $ p = a_l \cdot a_{l + 1} \cdot ... \cdot a_r $ 。然后她会要求 Eugene 计算在 $1 $ 和 $C$ 之间与 $p$ 互质的整数个数。
请帮助 Eugene 回答所有问题。
#### 输入格式
- 在输入的第一行有四个整数 $ n $ , $ m $ , $ C $ , $ q $ ( $ 1 \leq n, q \leq 10^5 $ , $ 1 \leq m \leq 2\cdot 10^4 $ , $ 1 \leq C \leq 10^5 $ ) —— 数组 $ a $ 的长度、$ a_{i} $ 的最大可能值、$ C $ 的值和查询次数.
- 第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_{i} \leq m $ ), 指数组 $ a $ 。
- 在接下来的 $ q $ 行中每一行代表一次查询。每个查询由两个整数 $ l $ 和 $ r $ ( $ 1 \leq l \leq r \leq n $ ) 组成。
#### 输出格式
- 对于每个询问,输出一个整数 —— Burenka 查询的答案。
**题目描述**
Eugene got Burenka an array $ a $ of length $ n $ of integers from $ 1 $ to $ m $ for her birthday. Burenka knows that Eugene really likes coprime integers (integers $ x $ and $ y $ such that they have only one common factor (equal to $ 1 $ )) so she wants to to ask Eugene $ q $ questions about the present.
Each time Burenka will choose a subsegment $ a_l, a_{l + 1}, \ldots, a_r $ of array $ a $ , and compute the product of these numbers $ p = a_l \cdot a_{l + 1} \cdot \ldots \cdot a_r $ . Then she will ask Eugene to count the number of integers between $ 1 $ and $ C $ inclusive which are coprime with $ p $ .
Help Eugene answer all the questions!
**输入输出格式**
**输入格式**
- 在输入的第一行有四个整数 $ n $ , $ m $ , $ C $ , $ q $ ( $ 1 \leq n, q \leq 10^5 $ , $ 1 \leq m \leq 2\cdot 10^4 $ , $ 1 \leq C \leq 10^5 $ ) —— 数组 $ a $ 的长度、$ a_{i} $ 的最大可能值、$ C $ 的值和查询次数.
- 第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_{i} \leq m $ ), 指数组 $ a $ 。
- 在接下来的 $ q $ 行中每一行代表一次查询。每个查询由两个整数 $ l $ 和 $ r $ ( $ 1 \leq l \leq r \leq n $ ) 组成。
**输出格式**
- 对于每个询问,输出一个整数 —— Burenka 查询的答案。
**输入输出样例**
**输入样例 #1**
```
5 5 5 3
1 2 3 2 5
1 1
2 4
4 5
```
**输出样例 #1**
```
5
2
2
```
**说明**
以下是样例的解释:
1. 在第一个查询中,乘积等于 $1$,与 $1,2,3,4,5$ 互质。
2. 在第二个查询中,乘积等于 $12$,它与 $1$ 和 $5$ 互质。
3. 在第三个查询中,乘积等于 $10$,它与 $1$ 和 $3$ 互质。**题意翻译** #### 题目描述 Eugene 给 Burenka 送上了他的生日礼物——一个长度为 $ n $ 的数组 $ a $ ,其中包含从 $ 1 $ 到 $ m $ 的整数。 Burenka 知道 Eugene 非常喜欢互质的两个整数(互质:指整数 $ x $ 和 $ y $ 的最大公约数为 $1$),所以她想问 Eugene $ q $ 关于礼物的问题。 每次 Burenka 都会选择数组 $a$ 的一个子段$ a_l, a_{l + 1}, \ldots, a_r $,并计算这些数字的乘积 $ p = a_l \cdot a_{l + 1} \cdot ... \cdot a_r $ 。然后她会要求 Eugene 计算在 $1 $ 和 $C$ 之间与 $p$ 互质的整数个数。 请帮助 Eugene 回答所有问题。 #### 输入格式 - 在输入的第一行有四个整数 $ n $ , $ m $ , $ C $ , $ q $ ( $ 1 \leq n, q \leq 10^5 $ , $ 1 \leq m \leq 2\cdot 10^4 $ , $ 1 \leq C \leq 10^5 $ ) —— 数组 $ a $ 的长度、$ a_{i} $ 的最大可能值、$ C $ 的值和查询次数. - 第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_{i} \leq m $ ), 指数组 $ a $ 。 - 在接下来的 $ q $ 行中每一行代表一次查询。每个查询由两个整数 $ l $ 和 $ r $ ( $ 1 \leq l \leq r \leq n $ ) 组成。 #### 输出格式 - 对于每个询问,输出一个整数 —— Burenka 查询的答案。 **题目描述** Eugene got Burenka an array $ a $ of length $ n $ of integers from $ 1 $ to $ m $ for her birthday. Burenka knows that Eugene really likes coprime integers (integers $ x $ and $ y $ such that they have only one common factor (equal to $ 1 $ )) so she wants to to ask Eugene $ q $ questions about the present. Each time Burenka will choose a subsegment $ a_l, a_{l + 1}, \ldots, a_r $ of array $ a $ , and compute the product of these numbers $ p = a_l \cdot a_{l + 1} \cdot \ldots \cdot a_r $ . Then she will ask Eugene to count the number of integers between $ 1 $ and $ C $ inclusive which are coprime with $ p $ . Help Eugene answer all the questions! **输入输出格式** **输入格式** - 在输入的第一行有四个整数 $ n $ , $ m $ , $ C $ , $ q $ ( $ 1 \leq n, q \leq 10^5 $ , $ 1 \leq m \leq 2\cdot 10^4 $ , $ 1 \leq C \leq 10^5 $ ) —— 数组 $ a $ 的长度、$ a_{i} $ 的最大可能值、$ C $ 的值和查询次数. - 第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_{i} \leq m $ ), 指数组 $ a $ 。 - 在接下来的 $ q $ 行中每一行代表一次查询。每个查询由两个整数 $ l $ 和 $ r $ ( $ 1 \leq l \leq r \leq n $ ) 组成。 **输出格式** - 对于每个询问,输出一个整数 —— Burenka 查询的答案。 **输入输出样例** **输入样例 #1** ``` 5 5 5 3 1 2 3 2 5 1 1 2 4 4 5 ``` **输出样例 #1** ``` 5 2 2 ``` **说明** 以下是样例的解释: 1. 在第一个查询中,乘积等于 $1$,与 $1,2,3,4,5$ 互质。 2. 在第二个查询中,乘积等于 $12$,它与 $1$ 和 $5$ 互质。 3. 在第三个查询中,乘积等于 $10$,它与 $1$ 和 $3$ 互质。
#### 题目描述
Eugene 给 Burenka 送上了他的生日礼物——一个长度为 $ n $ 的数组 $ a $ ,其中包含从 $ 1 $ 到 $ m $ 的整数。 Burenka 知道 Eugene 非常喜欢互质的两个整数(互质:指整数 $ x $ 和 $ y $ 的最大公约数为 $1$),所以她想问 Eugene $ q $ 关于礼物的问题。
每次 Burenka 都会选择数组 $a$ 的一个子段$ a_l, a_{l + 1}, \ldots, a_r $,并计算这些数字的乘积 $ p = a_l \cdot a_{l + 1} \cdot ... \cdot a_r $ 。然后她会要求 Eugene 计算在 $1 $ 和 $C$ 之间与 $p$ 互质的整数个数。
请帮助 Eugene 回答所有问题。
#### 输入格式
- 在输入的第一行有四个整数 $ n $ , $ m $ , $ C $ , $ q $ ( $ 1 \leq n, q \leq 10^5 $ , $ 1 \leq m \leq 2\cdot 10^4 $ , $ 1 \leq C \leq 10^5 $ ) —— 数组 $ a $ 的长度、$ a_{i} $ 的最大可能值、$ C $ 的值和查询次数.
- 第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_{i} \leq m $ ), 指数组 $ a $ 。
- 在接下来的 $ q $ 行中每一行代表一次查询。每个查询由两个整数 $ l $ 和 $ r $ ( $ 1 \leq l \leq r \leq n $ ) 组成。
#### 输出格式
- 对于每个询问,输出一个整数 —— Burenka 查询的答案。
**题目描述**
Eugene got Burenka an array $ a $ of length $ n $ of integers from $ 1 $ to $ m $ for her birthday. Burenka knows that Eugene really likes coprime integers (integers $ x $ and $ y $ such that they have only one common factor (equal to $ 1 $ )) so she wants to to ask Eugene $ q $ questions about the present.
Each time Burenka will choose a subsegment $ a_l, a_{l + 1}, \ldots, a_r $ of array $ a $ , and compute the product of these numbers $ p = a_l \cdot a_{l + 1} \cdot \ldots \cdot a_r $ . Then she will ask Eugene to count the number of integers between $ 1 $ and $ C $ inclusive which are coprime with $ p $ .
Help Eugene answer all the questions!
**输入输出格式**
**输入格式**
- 在输入的第一行有四个整数 $ n $ , $ m $ , $ C $ , $ q $ ( $ 1 \leq n, q \leq 10^5 $ , $ 1 \leq m \leq 2\cdot 10^4 $ , $ 1 \leq C \leq 10^5 $ ) —— 数组 $ a $ 的长度、$ a_{i} $ 的最大可能值、$ C $ 的值和查询次数.
- 第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_{i} \leq m $ ), 指数组 $ a $ 。
- 在接下来的 $ q $ 行中每一行代表一次查询。每个查询由两个整数 $ l $ 和 $ r $ ( $ 1 \leq l \leq r \leq n $ ) 组成。
**输出格式**
- 对于每个询问,输出一个整数 —— Burenka 查询的答案。
**输入输出样例**
**输入样例 #1**
```
5 5 5 3
1 2 3 2 5
1 1
2 4
4 5
```
**输出样例 #1**
```
5
2
2
```
**说明**
以下是样例的解释:
1. 在第一个查询中,乘积等于 $1$,与 $1,2,3,4,5$ 互质。
2. 在第二个查询中,乘积等于 $12$,它与 $1$ 和 $5$ 互质。
3. 在第三个查询中,乘积等于 $10$,它与 $1$ 和 $3$ 互质。**题意翻译** #### 题目描述 Eugene 给 Burenka 送上了他的生日礼物——一个长度为 $ n $ 的数组 $ a $ ,其中包含从 $ 1 $ 到 $ m $ 的整数。 Burenka 知道 Eugene 非常喜欢互质的两个整数(互质:指整数 $ x $ 和 $ y $ 的最大公约数为 $1$),所以她想问 Eugene $ q $ 关于礼物的问题。 每次 Burenka 都会选择数组 $a$ 的一个子段$ a_l, a_{l + 1}, \ldots, a_r $,并计算这些数字的乘积 $ p = a_l \cdot a_{l + 1} \cdot ... \cdot a_r $ 。然后她会要求 Eugene 计算在 $1 $ 和 $C$ 之间与 $p$ 互质的整数个数。 请帮助 Eugene 回答所有问题。 #### 输入格式 - 在输入的第一行有四个整数 $ n $ , $ m $ , $ C $ , $ q $ ( $ 1 \leq n, q \leq 10^5 $ , $ 1 \leq m \leq 2\cdot 10^4 $ , $ 1 \leq C \leq 10^5 $ ) —— 数组 $ a $ 的长度、$ a_{i} $ 的最大可能值、$ C $ 的值和查询次数. - 第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_{i} \leq m $ ), 指数组 $ a $ 。 - 在接下来的 $ q $ 行中每一行代表一次查询。每个查询由两个整数 $ l $ 和 $ r $ ( $ 1 \leq l \leq r \leq n $ ) 组成。 #### 输出格式 - 对于每个询问,输出一个整数 —— Burenka 查询的答案。 **题目描述** Eugene got Burenka an array $ a $ of length $ n $ of integers from $ 1 $ to $ m $ for her birthday. Burenka knows that Eugene really likes coprime integers (integers $ x $ and $ y $ such that they have only one common factor (equal to $ 1 $ )) so she wants to to ask Eugene $ q $ questions about the present. Each time Burenka will choose a subsegment $ a_l, a_{l + 1}, \ldots, a_r $ of array $ a $ , and compute the product of these numbers $ p = a_l \cdot a_{l + 1} \cdot \ldots \cdot a_r $ . Then she will ask Eugene to count the number of integers between $ 1 $ and $ C $ inclusive which are coprime with $ p $ . Help Eugene answer all the questions! **输入输出格式** **输入格式** - 在输入的第一行有四个整数 $ n $ , $ m $ , $ C $ , $ q $ ( $ 1 \leq n, q \leq 10^5 $ , $ 1 \leq m \leq 2\cdot 10^4 $ , $ 1 \leq C \leq 10^5 $ ) —— 数组 $ a $ 的长度、$ a_{i} $ 的最大可能值、$ C $ 的值和查询次数. - 第二行包含 $ n $ 个整数 $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_{i} \leq m $ ), 指数组 $ a $ 。 - 在接下来的 $ q $ 行中每一行代表一次查询。每个查询由两个整数 $ l $ 和 $ r $ ( $ 1 \leq l \leq r \leq n $ ) 组成。 **输出格式** - 对于每个询问,输出一个整数 —— Burenka 查询的答案。 **输入输出样例** **输入样例 #1** ``` 5 5 5 3 1 2 3 2 5 1 1 2 4 4 5 ``` **输出样例 #1** ``` 5 2 2 ``` **说明** 以下是样例的解释: 1. 在第一个查询中,乘积等于 $1$,与 $1,2,3,4,5$ 互质。 2. 在第二个查询中,乘积等于 $12$,它与 $1$ 和 $5$ 互质。 3. 在第三个查询中,乘积等于 $10$,它与 $1$ 和 $3$ 互质。