学步园

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4407

此题与poj 2773解法相似， 都是先分解素数再用dfs实现容斥原理， 只不过这题求的是数字的和而不再是数字个数， 其实做法还是换汤不换药， 至于第二种操作， 注意到总的操作数只有1000所以发生改变的数很少， 可以暴力处理。

#include <iostream>
#include <stack>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <queue>
#include <cstring>
#include <map>
#include <algorithm>

using namespace std;


const int N = 400005;
typedef long long LL;

LL c2(LL a) {
	return a * (a + 1) >> 1;
}

bool vis[N];
int fac[N];
int prime[N];
int cnt, tar, x, y;
LL ans;

void sieve(int n) {
	int m = sqrt(n + 0.5);
	for (int i = 2; i <= m; i++) if (!vis[i])
		for (int j = i * i; j <= n; j += i) vis[j] = 1;
}

int get_primes(int n) {
	sieve(n);
	int c = 0;
	for (int i = 2; i <= n; i++)
		if (!vis[i])
			prime[c++] = i;
	return c;
}

map<int, int> Map;

void dfs(int id, int now, LL& res, int v, bool flag) {
	if (id == cnt) return;
	dfs(id + 1, now, res, v, flag);
	int key = now * fac[id];

	if (flag)
		res += c2(v / key) * key;
	else
		res -= c2(v / key) * key;
	dfs(id + 1, key, res, v, !flag);
}

LL gao(int n) {
	LL res = 0;
	dfs(0, 1, res, n, 1);
	return c2(n) - res;
}

int gcd(int a, int b) {
	return b == 0 ? a : gcd(b, a % b);
}

void solve(pair<int, int> p) {
	int a = p.first, b = p.second;
	bool f1 = gcd(a, tar) == 1 && (a >= x && a <= y);
	bool f2 = gcd(b, tar) == 1 && (a >= x && a <= y);
	if (f1 && !f2) ans -= a;
	else if (f2 && !f1) ans += b;
	else if (f1 && f2) ans += (b - a);
}

int main() {
	int op, v, test, n, m;
	int c = get_primes(N - 5);
	scanf("%d", &test);
	while (test--) {
		Map.clear();
		scanf("%d%d", &n, &m);
		while (m--) {
			scanf("%d", &op);
			if (op == 1) {
				scanf("%d%d%d", &x, &y, &v);
				tar = v;
				cnt = 0;
				for (int i = 0; prime[i] <= v; i++) {
					while (v % prime[i] == 0) {
						fac[cnt++] = prime[i];
						v /= prime[i];
					}
				}
				cnt = unique(fac, fac + cnt) - fac;
				ans = gao(y) - gao(x - 1);
				for_each(Map.begin(), Map.end(), solve);					
				printf("%I64d\n", ans);
			}
			else {
				scanf("%d%d", &x, &v);
				Map[x] = v;
			}
		}
	}
	return 0;
}