bzoj#P4026. dC Loves Number Theory
dC Loves Number Theory
题目描述
dC 在秒了 BZOJ 上所有的数论题后,感觉萌萌哒,想出了这么一道水题,来拯救日益枯竭的水题资源。
给定一个长度为 的正整数序列 ,有 次询问,每次询问一段区间内所有元素乘积的(代表 到 中与 互质的数的个数) 。
由于答案可能很大,所以请对答案 。 (本题强制在线,所有询问操作的 都需要 上一次询问的答案 ,初始时,。)
输入格式
第一行,两个正整数,,,表示序列的长度和询问的个数。
第二行有 个正整数,第 个表示 。
下面 行,每行两个正整数,,表示询问 内所有元素乘积的。
输出格式
行,对于每个询问输出一个整数。
5 10
3 7 10 10 5
3 4
42 44
241 242
14 9
1201 1201
0 6
245 245
7 7
6 1
1203 1203
40
240
12
1200
2
240
4
4
1200
4
数据范围
对于 的数据,。