[51nod1678]lyk与gcd问题

这天，lyk又和gcd杠上了。 它拥有一个n个数的数列，它想实现两种操作。

1：将 ai

改为b。 2：给定一个数i，求所有gcd(i,j)=1

时的 aj

的总和。

Input

第一行两个数n，Q(1<=n,Q<=100000)。接下来一行n个数表示ai(1<=ai<=10^4)。接下来Q行，每行先读入一个数A(1<=A<=2)。若A=1，表示第一种操作，紧接着两个数i和b。(1<=i<=n,1<=b<=10^4)。若B=2，表示第二种操作，紧接着一个数i。(1<=i<=n)。第一行两个数n，Q(1<=n,Q<=100000)。

接下来一行n个数表示ai(1<=ai<=10^4)。

接下来Q行，每行先读入一个数A(1<=A<=2)。

若A=1，表示第一种操作，紧接着两个数i和b。(1<=i<=n,1<=b<=10^4)。

若B=2，表示第二种操作，紧接着一个数i。(1<=i<=n)。

Output

对于每个询问输出一行表示答案。对于每个询问输出一行表示答案。

Input示例

5312345241312453

12345

24

131

24

Output示例

979

7

把每个数的贡献拆成每个质因数的贡献，然后查询时加加减减即可

#include <cstdio>const int maxn = 100000 + 10;bool mark[maxn] = {false};int fr[maxn];int pri[maxn], prn = 0;void shai(){for(int i = 2; i < maxn; i++){if(!mark[i]){fr[i] = i;pri[++prn] = i;}for(int j = 1; j <= prn && i * pri[j] < maxn; j++){mark[i * pri[j]] = true;fr[i * pri[j]] = pri[j];if(i % pri[j] == 0) break;}}}int p[maxn], pcnt, Max;inline void GetFactor(int n){pcnt = 0;int t;while(n != 1){t = fr[n];p[++pcnt] = t;while(n % t == 0) n /= t;}Max = (1 << pcnt) - 1;}int num[maxn], sum[maxn] = {0};long long s = 0;inline void Update(int x, int y){y -= num[x];num[x] += y;for(int i = 1; i * i <= x; i++)if(x % i == 0){if(i * i == x) sum[i] += y;else{sum[i] += y;sum[x / i] += y;}}s += y;}inline long long solve(int x){GetFactor(x);long long ret = 0;for(int M, scnt, i = 0; i <= Max; i++){M = 1;scnt = 0;for(int j = 1; j <= pcnt; j++)if(i & 1 << j - 1){scnt++;M *= p[j];}if(scnt & 1) ret -= sum[M];else ret += sum[M];}return ret;}int main(){shai();int n, Q;scanf("%d %d", &n, &Q);int t;for(int i = 1; i <= n; i++){scanf("%d", num + i);s += num[i];}for(int i = 1; i <= n; i++)for(int j = i; j <= n; j += i)sum[i] += num[j];int op, x, y;while(Q--){scanf("%d %d", &op, &x);if(op == 1){scanf("%d", &y);Update(x, y);}else printf("%lld\n", solve(x));}return 0;}