题意：一个元素为 1~n 的数列{An}。有2种操作（1000次）：
1、求某段区间 [a,b] 中与 p 互质的数的和。
2、将数列中某个位置元素的值改变。
思路：先预处理求出1到400000全部数的质因子保存起来。
这个问题能够转化为求[1,R]之间与p不互素的数的和，这个能够用容斥原理来做，然后用区间和减去这个值就是答案，这是静态的做法。
假设有改动的话，我们注意到改动次数非常少。能够把全部改动用map存起来。对于当前的每次操作，把之前的改动遍历一遍就能够了，时间复杂度为O(m*m*logn)。
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<vector>
#include<map>
#include<queue>
#include<stack>
#include<string>
#include<map>
#include<set>
#define eps 1e-6
#define LL long long
using namespace std;
const int maxn = 500000;
//const int INF = 0x3f3f3f3f;
LL su[maxn];
bool vis[maxn];
map<int, int> ms;
vector<int> prime[maxn];
void init() {
su[0] = 0;
for(int i = 1; i <= 400000; i++) su[i] = su[i-1] + i;
memset(vis, 0, sizeof(vis));
for(int i = 2; i <= 400000; i++) if(!vis[i]) {
for(int j = i; j <= 400000; j+=i) vis[j] = 1, prime[j].push_back(i);
}
}
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a%b);
}
int n, m;
LL solve(int n, int p) {
LL ans = 0;
int sz = prime[p].size();
int s = (1<<sz);
for(int i = 1; i < s; i++) {
int cnt = -1, tmp = 1;
for(int j = 0; j < sz; j++) {
if((1<<j)&i) cnt *= -1, tmp *= prime[p][j];
}
if(tmp > n) continue;
int num = n/tmp;
ans = ans + (LL)cnt*((LL)tmp+(LL)num*(LL)tmp)*(LL)num/2;
}
return ans;
}
int main() {
//freopen("input.txt", "r", stdin);
int T; cin >> T;
init();
while(T--) {
cin >> n >> m;
ms.clear();
int op;
for(int i = 0; i < m; i++) {
scanf("%d", &op);
if(op == 1) {
int l, r, p; scanf("%d%d%d", &l, &r, &p);
LL ans = solve(r, p)-solve(l-1, p);
//cout << ans << endl;
for(map<int, int>::iterator it = ms.begin(); it != ms.end(); it++) {
if(it->first>=l && it->first<=r) {
if(gcd(it->first, p) != 1) ans -= it->first;
if(gcd(it->second, p) != 1) ans += it->second;
ans += it->first - it->second;
}
}
//cout << ans << endl;
//cout << su[r] << endl << su[l-1] << endl;
cout << su[r]-su[l-1]-ans << endl;
}
else {
int p, v; scanf("%d%d", &p, &v);
ms[p] = v;
}
}
}
return 0;
}