这天，lyk又和gcd杠上了。
它拥有一个n个数的数列，它想实现两种操作。
1：将
a
i
a_i
ai 改为
b
b
b。
2：给定一个数
i
i
i，求所有
g
c
d
(
i
,
j
)
=
1
gcd(i,j)=1
gcd(i,j)=1 时的
a
j
a_j
aj 的总和。
题解：
直接统计
g
c
d
(
i
,
j
)
=
=
1
gcd(i,j)==1
gcd(i,j)==1的和不太好下手，因此，我们从反面入手，先统计处
g
c
d
(
i
,
j
)
!
=
1
gcd(i,j)!=1
gcd(i,j)!=1的和。
如何得到这个和呢？我们可以采用容斥原理。首先我们将
i
i
i进行质因数分解。假设，
i
=
60
i=60
i=60，有2， 3， 5这三个质因数，那么满足
g
c
d
(
i
,
j
)
!
=
1
gcd(i,j)!=1
gcd(i,j)!=1的和就是
S
(
2
)
+
S
(
3
)
+
S
(
5
)
−
S
(
2
∗
3
)
−
S
(
2
∗
5
)
−
S
(
3
∗
5
)
+
S
(
2
∗
3
∗
5
)
S(2)+S(3)+S(5)-S(2*3)-S(2*5)-S(3*5)+S(2*3*5)
S(2)+S(3)+S(5)−S(2∗3)−S(2∗5)−S(3∗5)+S(2∗3∗5)，这里的
S
(
x
)
S(x)
S(x)表示下标能够被
x
x
x整除的数的和。比如
S
(
2
)
=
a
[
2
]
+
a
[
4
]
+
a
[
6
]
…
S(2)=a[2]+a[4]+a[6]\dots
S(2)=a[2]+a[4]+a[6]…。那么我们在每次询问时维护这个总和和数组即可。
实现细节见代码：
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1e5 + 10;
std::vector<int> g[MAXN];
int a[MAXN], primes[MAXN], cnt, val[MAXN], now[MAXN];
bool vis[MAXN];
void sieve(int n) {
for (int i = 2; i <= n; i++) {
if (!vis[i]) primes[cnt++] = i;
for (int j = 0; primes[j] <= n / i; j++) {
vis[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
void init(int n) {
for (int i = 2; i <= n; i++) {
for (int j = 2; j * j <= i; j++) {
if (i % j == 0) {
g[i].push_back(j);
if (j * j != i) {
g[i].push_back(i / j);
}
}
}
g[i].push_back(i);
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int n, q;
sieve(1e5 + 5);
init(1e5 + 5);
cin >> n >> q;
ll sum = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum += a[i];
int len = g[i].size();
for (int j = 0; j < len; j++) {
val[g[i][j]] += a[i];
}
}
while (q--) {
int op;
cin >> op;
if (op == 1) {
int pos, x;
cin >> pos >> x;
sum += x - a[pos];
int len = g[pos].size();
for (int i = 0; i < len; i++) { // 维护val数组
val[g[pos][i]] -= a[pos];
val[g[pos][i]] += x;
}
a[pos] = x;
}
else {
ll ans = 0, num = 0;
int x;
cin >> x;
if (x == 1) {
cout << sum << endl;
continue;
}
for (int i = 0; i < cnt; i++) {
if (x % primes[i] == 0) {
now[num++] = primes[i];
while (x % primes[i] == 0) {
x /= primes[i];
}
}
if (x < 2) break;
}
for (int i = 0; i < 1 << num; i++) {
int cur = 0, p = 1;
for (int j = 0; j < num; j++) {
if (i & (1 << j)) {
cur++;
p *= now[j];
}
}
if (cur % 2) {
ans += val[p];
}
else {
ans -= val[p];
}
}
cout << sum - ans << endl;
}
}
return 0;
}