题目

数据范围

分析

时限5000ms。

我们注意到\(a_{i}初始值以及x小于等于600且非零\)

也就是说，\(a_{i}\)的质因数一定小于600，而600以内的质因数只有109个。

那么考虑常用于区间修改的线段树。

用线段树来维护某个位置的某个质因数的总乘积，以及某个质因数出现的位置的个数。

时间复杂度\(O(QlogN·109)\)
#include <cmath>

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <queue>

const long long maxlongint=2147483647;

const long long mo=100000007;

const long long N=50005;

using namespace std;

struct ddx

{

	long long a[120],v[120],lazy[120],sum[120];

}tree[50005];

long long ss[80000],n,m,ny[1000005],belong[1000005];

long long ans,re[10005];

bool b[1000005];

long long mi(long long x,long long y)

{

	long long sum=1;

	while(y)

	{

		if(y&1) sum=x*sum%mo;

		x=x*x%mo;

		y/=2;

	}

	return sum;

}

long long put(long long v,long long l,long long r,long long x,long long y,long long z)

{

	if(l==r)

	{

		tree[v].a[y]=z;

		tree[v].v[y]=tree[v].v[y]*mi(ss[y],z)%mo;

		tree[v].sum[y]=1;

		return 0;

	}

	long long mid=(l+r)/2;

	if(x<=mid)

		put(v*2,l,mid,x,y,z);

			else put(v*2+1,mid+1,r,x,y,z);

	for(long long i=1;i<=109;i++)

	{

		tree[v].a[i]=(tree[v*2].a[i]+tree[v*2+1].a[i])%mo;

		tree[v].v[i]=tree[v*2].v[i]*tree[v*2+1].v[i]%mo;

		tree[v].sum[i]=tree[v*2].sum[i]+tree[v*2+1].sum[i];

	}

}

long long down(long long v,long long mid,long long l,long long r,long long y)

{

	if(!tree[v].lazy[y]) return 0;

	long long z=tree[v].lazy[y];

	tree[v*2].a[y]+=z*(mid-l+1);

	tree[v*2+1].a[y]+=z*(r-mid);

	tree[v*2].v[y]=tree[v*2].v[y]*mi(ss[y],z*(mid-l+1))%mo;

	tree[v*2+1].v[y]=tree[v*2+1].v[y]*mi(ss[y],z*(r-mid))%mo;

	tree[v*2].lazy[y]+=z;

	tree[v*2+1].lazy[y]+=z;

	tree[v*2].sum[y]=(mid-l+1);

	tree[v*2+1].sum[y]=(r-mid);

	tree[v].lazy[y]=0;

}

long long change(long long v,long long l,long long r,long long x,long long x1,long long y,long long z)

{

	if(l==x && r==x1)

	{

		tree[v].a[y]=(tree[v].a[y]+z*(r-l+1))%mo;

		tree[v].v[y]=tree[v].v[y]*mi(ss[y],z*(r-l+1))%mo;

		tree[v].sum[y]=(r-l+1);

		tree[v].lazy[y]+=z;

		return 0;

	}

	long long mid=(l+r)/2;

	for(long long i=1;i<=109;i++) down(v,mid,l,r,i);

	if(x1<=mid)

		change(v*2,l,mid,x,x1,y,z);

	else

	if(x>mid)

		change(v*2+1,mid+1,r,x,x1,y,z);

	else

		change(v*2,l,mid,x,mid,y,z),change(v*2+1,mid+1,r,mid+1,x1,y,z);

	for(long long i=1;i<=109;i++)

	{

		tree[v].a[i]=(tree[v*2].a[i]+tree[v*2+1].a[i])%mo;

		tree[v].v[i]=tree[v*2].v[i]*tree[v*2+1].v[i]%mo;

		tree[v].sum[i]=tree[v*2].sum[i]+tree[v*2+1].sum[i];

	}

}

long long find(long long v,long long l,long long r,long long x,long long x1)

{

	if(l==x && r==x1)

	{

		for(long long i=1;i<=109;i++)

		{

			if(tree[v].sum[i])

				ans=ans*tree[v].v[i]%mo*mi(ny[ss[i]],tree[v].sum[i])%mo*mi(ss[i]-1,tree[v].sum[i])%mo;

		}

		return 0;

	}

	long long mid=(l+r)/2;

	for(long long i=1;i<=109;i++) down(v,mid,l,r,i);

	if(x1<=mid)

		find(v*2,l,mid,x,x1);

	else

	if(x>mid)

		find(v*2+1,mid+1,r,x,x1);

	else

		find(v*2,l,mid,x,mid),find(v*2+1,mid+1,r,mid+1,x1);

	for(long long i=1;i<=109;i++)

	{

		tree[v].a[i]=(tree[v*2].a[i]+tree[v*2+1].a[i])%mo;

		tree[v].v[i]=tree[v*2].v[i]*tree[v*2+1].v[i]%mo;

		tree[v].sum[i]=tree[v*2].sum[i]+tree[v*2+1].sum[i];

	}

}

int main()

{

	memset(b,true,sizeof(b));

	b[0]=0;

	b[1]=0;

	for(long long i=2;i<=10000;i++)

	{

		if(b[i])

		{

			ss[++ss[0]]=i;

			ny[i]=mi(i,mo-2);

			belong[i]=ss[0];

		}

		for(long long j=1;j<=ss[0];j++)

		{

			if(i*ss[j]<=10000)

				b[i*ss[j]]=false;

					else break;

			if(!(i%ss[j])) break;

		}

	}

	scanf("%lld",&n);

		for(long long i=1;i<=50001;i++)

			for(long long j=1;j<=110;j++)

				tree[i].v[j]=1;

		for(long long j=1;j<=n;j++)

		{

			scanf("%lld",&re[j]);

			long long p=re[j];

			if(b[p])

			{

				put(1,1,n,j,belong[p],1);

			}

			else

			{

				for(long long k=1;ss[k]<=sqrt(re[j]) && p>1;k++)

				{

					long long w=0;

					while(!(p%ss[k]))

					{

						p/=ss[k];

						w++;

					}

					if(w)

					{

						put(1,1,n,j,k,w);

					}

				}

				if(p>1)

				{

					put(1,1,n,j,belong[p],1);

				}

			}

		}

		long long q;

		scanf("%lld",&q);

		for(long long i=1;i<=q;i++)

		{

			long long t,x,y,z;

			scanf("%lld%lld%lld",&t,&x,&y);

			if(t)

			{

				ans=1;

				find(1,1,n,x,y);

				printf("%lld\n",ans);

			}

			else

			{

				scanf("%lld",&z);

				long long p=z;

				if(b[p])

				{

					change(1,1,n,x,y,belong[p],1);

				}

				else

				{

					for(long long k=1;ss[k]<=sqrt(z) && p>1;k++)

					{

						long long w=0;

						while(!(p%ss[k]))

						{

							p/=ss[k];

							w++;

						}

						if(w)

						{

							change(1,1,n,x,y,k,w);

						}

					}

					if(p>1)

					{

						change(1,1,n,x,y,belong[p],1);

					}

				}

			}

		}

}
巴特西

【NOIP2016提高组A组7.16】第三条跑道

题目

数据范围

分析

最新文章

热门文章
