第一道容斥原理的题目。
题意：
有一个元素为 1~n 的数列{An}，有2种操作（1000次）：
1、求某段区间 [a,b] 中与 p 互质的数的和。
2、将数列中某个位置元素的值改变。
解题思路：
对于操作1，解的性质满足区间减法，则我们只需要考虑如何求 [1,n] 中与 p 互质的数的和即可。
考虑到与 p 互质的数不太好解，于是可以通过先求出与 p 不互质的数的和，然后与总和作差得到。
而一个数 x 若与 p 不互质，当且仅当两者素因子的集合有交集。
设 p 的素因子是{P1,P2,…,Pk}，于是与 p 不互质的数的素因子集合可以表示成 {P1} U {P2} U … U {Pk}。
那么与 p 不互质的数的集合可以表示成 W = { P1的倍数 } U { P2的倍数 } U … U { Pk的倍数 }。
其中，{ Pk的倍数 } = { Pk*1 } + { Pk*2 } + … + { Pk*Mk } ( Pk*Mk<=n && Pk*(Mk+1)>n )。
从而，ans = sum{ W }。
于是可以通过容斥原理，求得问题的解。
举个简单的例子，假如 k=2，则 ans = 【sum{ P1的倍数 } + sum{ P2的倍数 } - sum{ P1*P2的倍数 }】。
其中，XX的倍数可以通过等差公式求得。
对于操作2，由于操作比较少，我们可以保存这些操作，当遇到要求和的时候，我们遍历之前保存的操作，找到在区间中改变的值，对应修改即可。
[cpp]
#include