题目描述
众所周知,duxing201606得到了某知名数学家的真传,现在她有了无穷的力量.现在她面前有一个数组a,duxing201606打算施法,有两种魔法,
第一种:把[l,r]区间的每个数变成它的f函数,即a[i]=f(a[i]).
第二种:查询区间[l,r]中a[i]的和.
f(x)是1到x中与x互质的数的个数。f（1）=1.
输入
多组数据,请读到文件末尾.一个数n表示a的长度,(1<=n<=5e5).下一行n个数表示a[i],(1<=a[i]<=1e7).再下一行,一个q,表示执行的魔法个数.接下来q(1<=q<=5e5)行,先是操作种类,1表示魔法1,2表示魔法2,然后是区间l,r(1<=l<=r<=n)
输出
对于每个第二种操作,输出答案
样例输入
5
1 2 3 4 5
3
2 2 4
1 2 5
2 4 5
样例输出
9
6
来源/分类
浙江理工大学月赛