记录编号	254723	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015] gcd array	最终得分	100
用户昵称	assassain	是否通过	通过
代码语言	C++	运行时间	1.415 s
提交时间	2016-04-25 17:01:42	内存使用	1.58 MiB

#define MAXN 50010UL
#include <cstdio>
#include <vector>

using namespace std;

typedef long long ll;
int n, Q, pr[MAXN], u[MAXN];
ll c[MAXN];
bool vis[MAXN];
vector <int> V[MAXN];

void Pre(int r) {
	u[1] = 1;
	for(int i = 2 ; i <= r ; ++ i) {
		if(!vis[i]) pr[++ pr[0]] = i, u[i] = -1;
		for(int j = 1 ; j <= pr[0] && 1ll*i*pr[j] <= r ; ++ j) {
			int nx = i*pr[j];
			vis[nx] = true;
			if(!(i%pr[j])) {
				u[nx] = 0;
				break;
			} else u[nx] = -u[i];
		}
	}
	for(int i = 1 ; i <= r ; ++ i) {
		for(int j = i ; j <= r ; j += i) {
			if((j/i)>=i) V[j].push_back(i);
 			if((j/i)>i) V[j].push_back(j/i);
		}
	}
	return;
}

void Insert(int x, ll k) {
	while(x<=n) {
		c[x] += k;
		x += x&(-x);
	}
	return;
}

ll Find(int x) {
	ll ret = 0;
	while(x>0) {
		ret += c[x];
		x -= x&(-x);
	}
	return ret;
}

void Add(int n, int d, int v) {
	if((n%d)||v==0) return;
	int len = V[n/d].size();
	for(int i = 0 ; i < len ; ++ i) Insert(V[n/d][i]*d, 1ll*u[V[n/d][i]]*v);
	return;
}

ll Ask(int x) {
	ll ret = 0;
	for(int i = 1, _last ; i <= x ; i = _last+1) {
		_last = x/(x/i);
		ret += 1ll*(x/i)*(Find(_last)-Find(i-1));
	}
	return ret;
}

int main() {
	freopen("gcd_array.in", "r", stdin);
	freopen("gcd_array.out", "w", stdout);
	int op, x, y, z;
	Pre(50000);
	scanf("%d%d", &n, &Q);
	for(int i = 1 ; i <= Q ; ++ i) {
		scanf("%d", &op);
		if(op==1) scanf("%d%d%d", &x, &y, &z), Add(x, y, z);
		else scanf("%d", &x), printf("%lld\n", Ask(x));
	}
	return 0;
}