记录编号	406400	评测结果	AAAAAAAAAA
题目名称	[HZOI 2015] gcd array	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.563 s
提交时间	2017-05-18 16:48:26	内存使用	2.07 MiB

#include<cstdio>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
typedef long long ll;
const int N=50010;
struct bit{
	ll a[N];
	void add(int p,int d){
		for (;p<N;p+=p&-p) a[p]+=d;
	}
	ll sum(int r){
		ll ans=0;
		for (;r;r-=r&-r) ans+=a[r];
		return ans;
	}
}T;
ll tag[N];
int n,q,u[N],p[N],cnt,size;
bool isp[N];
vector<int> fac[N];
void init(){
	u[1]=1;
	for (int i=2;i<=n;i++){
		if (!isp[i]) p[++cnt]=i,u[i]=-1;
		for (int j=1;j<=cnt&&i*p[j]<=n;j++){
			int x=i*p[j];isp[x]=1;
			if (i%p[j]) u[x]=-u[i];
			else{u[x]=0;break;}
		}
	}
	for (int i=1;i<=n;i++) if (u[i])
	for (int j=i;j<=n;j+=i)
		fac[j].push_back(i);
}
int main()
{
	freopen("gcd_array.in","r",stdin);
	freopen("gcd_array.out","w",stdout);
	scanf("%d%d",&n,&q);
	size=sqrt(n);//整块打标记,散块放进bit 
	init();
	while (q--){
		int tp,x,d,v;
		scanf("%d%d",&tp,&x);
		if (tp==1){
			scanf("%d%d",&d,&v);
			if (x%d) continue;
			x/=d;
			for (int i=fac[x].size()-1;i>=0;i--){
				int p=fac[x][i]*d;
				if (p<=size) tag[p]+=u[p/d]*v;else
				for (int q=p;q<=n;q+=p) T.add(q,u[p/d]*v);
			}
		}
		else{
			ll ans=T.sum(x);
			for (int i=1;i<=size;i++) ans+=x/i*tag[i];
			printf("%lld\n",ans);
		}
	}
	return 0;
}