| 题目名称 | 3715. 简单数论题 |
|---|---|
| 输入输出 | simple.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 1500 ms (1.5 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 op_组撒头屯
于2022-07-12加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：1， 提交：1， 通过率：100% | ||||
 op_组撒头屯 |
100 | 1.864 s | 9.63 MiB | C++ |
| 关于 简单数论题 的近10条评论(全部评论) |
|---|
【题目描述】
给出一个长度为$n$的序列$a$，$q$次询问$\prod_{i=l}^r {lcm(a_i,x)}$的值。
答案对$10^9+7$取模。
【输入格式】
第一行两个整数$n,q$。
第二行$n$个整数$a_i$。
接下来$q$行，每行三个整数$l,r,x$。
【输出格式】
$q$行，一行一个答案。
【样例输入1】
5 5 12 8 9 14 21 1 5 2 1 3 3 3 5 7 1 5 6 2 3 7
【样例输出1】
1016064 2592 18522 9144576 3528
【样例输入2】
10 10 47 47 47 3 7 19 2 7 31 31 1 3 53 4 4 61 2 8 73 6 7 53 1 5 47 2 5 73 5 6 71 7 7 67 4 7 83 1 9 59
【样例输出2】
456856666 183 802334105 106742 816245119 365992530 670453 134 871739899 194416112
【样例输入3】
10 10 2 13 13 2 3 17 11 19 19 7 4 8 1 1 2 7 6 7 37 9 10 7 1 8 9 3 8 47 5 8 2 3 6 9 4 5 25 4 5 8
【样例输出3】
21318 1274 256003 931 819082258 40076077 170544 2899962 3750 192
【样例输入4】
10 10 14 39 31 30 3 21 19 17 35 2 1 3 10 6 6 19 2 4 3 6 8 18 1 10 2 5 6 49 2 6 8 7 9 26 3 6 12 1 1 10
【样例输出4】
8463000 399 108810 13186152 23723126 21609 437603581 198696680 22498560 70
【样例说明】
对于样例一的第二个查询，答案是：
$lcm(12,3)×lcm(8,3)×lcm(9,3)$
$=12×24×9$
$=2592$
【数据规模与约定】
对于$30\%$的数据：$1≤n,q,ai,x≤100$。
对于$100\%$的数据：$1≤l≤r≤n,1≤n,q,ai,x≤2×10^5$。
【来源】
luogu P6217，数据规模调整