HDU4407

【题意】给出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;
}