bzoj#P4026. dC Loves Number Theory

dC Loves Number Theory

题目描述

dC 在秒了 BZOJ 上所有的数论题后,感觉萌萌哒,想出了这么一道水题,来拯救日益枯竭的水题资源。

给定一个长度为 nn 的正整数序列 AA,有 qq 次询问,每次询问一段区间内所有元素乘积的Φ\Phi Φn\Phi _n代表 11nn 中与 nn 互质的数的个数) 。

由于答案可能很大,所以请对答案 mod106+777\bmod 10^6 +777。 (本题强制在线,所有询问操作的 l,rl,r 都需要 \oplus 上一次询问的答案 lastanslastans,初始时,lastans=0lastans = 0。)

输入格式

第一行,两个正整数,nnqq,表示序列的长度和询问的个数。

第二行有 nn 个正整数,第 ii 个表示 AiA_i

下面 qq 行,每行两个正整数,l,rl,r,表示询问 [llastans,rlastans][l \oplus {lastans},r \oplus {lastans}] 内所有元素乘积的Φ\Phi

输出格式

qq 行,对于每个询问输出一个整数。

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

数据范围

对于 100%100\% 的数据,1N50000,1Q100000,1Ai1061\le N\le 50000,1\le Q\le 100000,1\le A_i\le 10^6