文理学院程序设计在线练习


诚哥很无聊

Time Limit: 10 Second(s)    Memory Limit: 128 MB

Total Submission(s): 9   Accepted Submission(s): 3
Problem Description

诚哥赢得了圣杯,实现了所有的愿望,开始觉得很无聊。因此他发明了下面的游戏。
对数X进行一次变换被定义为统计集合{i|1<=i<=X&&gcd(i,X)==1}的大小。
给出一个大小为N的数组。
可以对数组进行2种操作:
1.对L~R的数做一次变换
2.查询L~R的和

Input

第一行一个字母T,表示测试数据的数量。
接下来有T组数据。
每一组数据的第一行有2个整数N,Q表示数组的长度和操作的次数
接下来1行N个整数表示数组的第i个元素。数组从1开始编号。
接下来Q行每行代表1个操作。
每一行3个整数mode,L,R;
如果mode==1,进行操作1,对L~R的数做一次变换。
如果mode==2,进行操作2,查询数组在L~R的和。
数据范围:
0<T<20
N,Q<1e5
0<Arr[i]<1e5
1<=L,R<=N

Output

对每一组操作2,输出数组在L~R的和。

Sample Input
1
5 5
1 2 3 4 5
1 1 2
2 1 5
1 3 5
1 4 5
2 2 3
Sample Output
14
3
Hint

对于样例,设变换函数为F(x),F[1]=|{1}|,F[2]=|{1}|,F[3]=|{1,2}|,F[4]=|{1,3}|,F[5]=|{1,2,3,4}|
执行了第1条操作后数组变成了{1,1,3,4,5}
执行了第2条操作后输出1+1+3+4+5=14
执行了第3条操作后数组变成了{1,1,2,2,4}
执行了第4条操作后数组变成了{1,1,2,1,2}
执行了第5条操作后输出1+2=3

Source

第12届校赛