【题意】给出N(<=400000)个数字1~N,a[i] = i组成的数列;m(<=1000)个操作:
1 x y p:查询区间[x,y]中与p互质的数的所有数的和;
2 x y:把a[x]修改为y
【分析】首先,可以把修改操作孤立,由于总操作不超过1000个,那么每次询问分成两部分:1.没有任何修改的[x,y]的答案;2.处理之前所有修改;这样就只要求出没有任何修改的值就解决了。
这样问题变成了求[x,x+1,x+2…y-1,y]中与p互质的数的和。其实和欧拉phi函数很像,而那个其实是可以用容斥原理+分解质因数解决的。
把p分解质因数,去掉[x,y]中所有是p的质因数的倍数的数字全部去掉即可,这步可以用等差数列求和公式O(1)算出,但是直接计算去掉会有很多重复部分,这时候就要使用容斥原理,求出每个质因数的搭配,a,b,c,d,a*b,a*c,a*d…a*b*c*d;对于每个搭配有奇数个前面符号为正否则为负。
由于1~400000的数分解质因素不会超过6种,所以容斥的复杂度为n* 2^n很小可以忽略。
总的复杂度为m*m+m*sqrt(ai)
【AC CODE】561ms
#include <bits/stdc++.h> using namespace std; typedef long long LL; #define rep(i,a,n) for(int i = a; i < n; i++) #define repe(i,a,n) for(int i = a; i <= n; i++) #define per(i,n,a) for(int i = n; i >= a; i--) #define clc(a,b) memset(a,b,sizeof(a)) const int INF = 0x3f3f3f3f, MAXN = 1000+10; int gcd(int a, int b) { while(b) { a %= b; if(a < b) swap(a,b); } return a; } vector<int> p; void get_p(int n) { int m = sqrt(n+0.5); p.clear(); for(int i = 2; i <= m; i++) { if(n % i == 0) { p.push_back(i); while(n % i == 0) n /= i; } } if(n > 1) p.push_back(n); } inline LL count(LL x, LL y, LL v) { LL n = y/v-(x-1)/v,a = ((x-1)/v+1)*v; if(a > y) return 0; return n*a+n*(n-1)*v/2; } LL sloved(LL x, LL y, int c) { get_p(c); int sz = p.size(),all = 1<<sz; LL ans = 0; rep(s,1,all) { int bit = 0,tmp = 1; rep(i,0,sz) { if(s&(1<<i)) { bit++; tmp *= p[i]; } } if(bit&1) ans += count(x,y,tmp); else ans -= count(x,y,tmp); } return (x+y)*(y-x+1)/2-ans; } map<int,int> cg; LL query(int x, int y, int c) { LL ans = sloved(x,y,c); for(auto it = cg.lower_bound(x); it != cg.end() && it->first <= y; it++) { int u = it->first, v = it->second; if(1 == gcd(u,c) && 1 != gcd(v,c)) ans -= u; else if(1 == gcd(u,c) && 1 == gcd(v,c)) ans -= u,ans += v; else if(1 != gcd(u,c) && 1 == gcd(v,c)) ans += v; } return ans; } int main() { #ifdef SHY freopen("d:\\1.txt", "r", stdin); #endif int t; scanf("%d", &t); while(t--) { int n,q; scanf("%d %d", &n, &q); cg.clear(); while(q--) { int op,x,y; scanf("%d %d %d", &op, &x, &y); if(1 == op) { int v; scanf("%d", &v); printf("%I64d\n", query(x,y,v)); } else cg[x] = y; } } return 0; }