2101. [HZOI 2015] 质数序列 PrimeSeq

【题目描述】

给出一个长度为n序列,维护一种操作和查询,若操作为Modify x y,则将在x位置上的数乘y,若为Query l r p,则输出l到r区间全部数的乘积中个小于等于p的质因子的幂次之和,如l到r的乘积为24,即为2^3*3^1,若p=1,则结果为0,若p=2,则结果为3.

【输入格式】

第一行两个数n,m分别为序列的长度和操作的次数,接下来1行,n个数为初始序列的每个数,接下来m行,若操作为Modify,则后有两个数x,y,若为Query,则后面有三个数l,r,q.

【输出格式】

对应所有的Query操作,输出对应的结果,每行一个.

【样例输入】

3 2



24 24 3



Modify 3 8



Query 1 3 2

【样例输出】

9

【提示】

样例说明:

 对第三个数乘8后为24,1到3的乘积分解质因数为2^9*3^3,那么小于等于2的质因子只有2,幂次为9故结果为9.

数据范围约定:

 对于20%的数据,n<=10,m<=10,询问的乘积不会超过10^5.

 对于另外40%的数据,n<=100000,m<=50000,询问的乘积不会超过64位整形.

 对于剩余的数据,n<=100000,m<=200000,询问的乘积不会超过10^10000

 对于全部数据保证不会出现超过400的质因子.

【来源】

by stdafx