主题

主题

 
   

4026: dC Loves Number Theory

Description

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

竭的水题资源。 

  给定一个长度为 n的正整数序列A,有q次询问,每次询问一段区间内所有元素乘积的

φ(φ(n)代表1~n 中与n互质的数的个数) 。由于答案可能很大,所以请对答案 mod 10^6 + 

777。 (本题强制在线,所有询问操作的l,r都需要 xor上一次询问的答案 lastans,初始时,

lastans = 0) 

Input

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

第二行有N 个正整数,第i个表示Ai. 

下面Q行,每行两个正整数,l r,表示询问[l ^ lastans,r ^ lastans]内所有元素乘积的φ 

Output

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

Sample Input

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

Sample Output

40

240

12

1200

2

240

4

4

1200

4

HINT

1 <= N <= 50000

1 <= Q <= 100000

1 <= Ai <= 10^6


个人解法:

首先自然是想到通过欧拉函数是积性函数去维护一个积什么的,不过欧拉函数不是一个完全积性函数,所以想了很久没有想出来。

后来发现A[i]<=1e6,觉得可以把每个数字拆开,于是想到了欧拉函数的另一个公式,phi(x)=x*pai((p[i]-1)/p[i])。

然后发现只需要维护区间内的不同的质数的(p[i]-1)/p[i]就好了。

于是想到主席树。曾经做过的一些维护last处理区间不同数字的问题。然后这题就瞎YY了一下。同样主席树维护区间积就可以了。

刚开始每一次除法都求一个逆元。然后本机生成随机数据死活1.5s。不知道为什么。后来猛然发现在主席树里面求了逆元,所以复杂度是O(nlog^2n)的……

然后筛法求逆元去了。就过了……


代码如下:

http://www.lydsy.com/JudgeOnline/problem.php?id=4026

 
 
评论