1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
| #include <bits/stdc++.h>
#define dbg(x) std::cerr << #x << " = " << x << "\n"
using namespace std;
typedef long long ll;
const int N = 100000 + 10;
int t, n, m, a[N];
int mu[N], prime[N], np[N], cnt, smallest[N];
void pre() {
np[1] = mu[1] = 1;
for(int i = 2; i <= 100000; i++) {
if(!np[i]) prime[++cnt] = i, mu[i] = -1, smallest[i] = i;
for(int j = 1; j <= cnt && i * prime[j] <= 100000; j++) {
np[i * prime[j]] = 1; smallest[i * prime[j]] = prime[j];
if(i % prime[j] == 0) {mu[i * prime[j]] = 0;break;}
else mu[i * prime[j]] = -mu[i];
}
}
}
vector <int> divisior, v;
vector <int> pool[N];
int cont[N];
int sz, ans;
int bs(int id, int x) {
if(pool[id].size() == 0) return 0;
if(pool[id][(int)pool[id].size() - 1] < x) return pool[id].size();
if(pool[id][0] >= x) return 0;
int l = 0, r = (int)(pool[id].size()) - 1, ans = 0;
while(l <= r) {
int mid = (l + r) >> 1;
if(pool[id][mid] < x) ans = mid, l = mid + 1;
else r = mid - 1;
}
return ans + 1;
}
int query(int id, int l, int r) {
int ans = min(bs(id, r + 1) - bs(id, l), (int)pool[id].size());
return ans;
}
void dfs(int cur, int d) {
if(cur == sz) {
if(!cont[d]) cont[d] = true, v.push_back(d);
return ;
}
dfs(cur + 1, d * divisior[cur]);
dfs(cur + 1, d);
}
void dfs2(int cur, int d, int l, int r) {
if(cur == sz) {
if(!cont[d]) cont[d] = 1, v.push_back(d), ans += mu[d] * query(d, l, r);
return ;
}
dfs2(cur + 1, d * divisior[cur], l, r);
dfs2(cur + 1, d , l, r);
}
void solve() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) scanf("%d", &a[i]);
for(int i = 1; i <= 100000; i++) pool[i].clear();
for(int i = 1; i <= n; i++) {
v.clear(); divisior.clear(); int cp = a[i];
while(cp != 1) {
divisior.push_back(smallest[cp]);
cp /= smallest[cp];
}
sz = divisior.size(); dfs(0, 1);
for(int j = 0; j < v.size(); j++) {
pool[v[j]].push_back(i); cont[v[j]] = 0;
}
}
int d = 0;
while(m--) {
int l, r, x; scanf("%d%d%d", &l, &r, &x);
l ^= d, r ^= d, x ^= d;
int curx = x; ans = 0;
divisior.clear(); v.clear();
while(curx != 1) {
divisior.push_back(smallest[curx]);
curx /= smallest[curx];
}
sz = divisior.size();
dfs2(0, 1, l, r);
d = ans;
printf("%d\n", d);
for(int j = 0; j < v.size(); j++) cont[v[j]] = 0;
}
for(int i = 0; i < v.size(); i++) cont[v[i]] = 0;
}
int main() {
scanf("%d", &t);
pre();
while(t--) solve();
return 0;
}
|