题目描述

　　给你一个长度为\(n\)的数列，第\(i\)个数为\(a_i\)。每个数的质因子都只有前\(60\)个质数。有\(q\)个询问，每次给你\(l,r\)，求\(\varphi(\prod_{i=l}^ra_i)\)

　　模数为\(19961993\)，是个质数

　　\(n=100000,q\leq 100000\)

题解

　　水题

　　用线段树维护区间乘积和这个区间的乘积的质因子（每个质数有没有出现）

　　然后乱搞

　　时间复杂度：\(O(q\log n)\)

代码

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#include<ctime>

#include<cstdlib>

#include<utility>

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

typedef pair<ll,ll> pll;

ll p=19961993;

ll pp=p;

ll fp(ll a,ll b)

{

	ll s=1;

	while(b)

	{

		if(b&1)

			s=s*a%p;

		a=a*a%p;

		b>>=1;

	}

	return s;

}

int pri[110];

ll a[110];

ll s[500010];

ll o[500010];

int ls(int x){return x*2;}

int rs(int x){return x*2+1;}

void build(int p=1,int l=1,int r=100000)

{

	if(l==r)

	{

		s[p]=3;

		o[p]=2;

		return;

	}

	int mid=(l+r)>>1;

	build(ls(p),l,mid);

	build(rs(p),mid+1,r);

	s[p]=s[ls(p)]*s[rs(p)]%pp;

	o[p]=o[ls(p)]|o[rs(p)];

}

void change(int p,int x,ll v1,ll v2,int L=1,int R=100000)

{

	if(L==R)

	{

		s[p]=v1;

		o[p]=v2;

		return;

	}

	int mid=(L+R)>>1;

	if(x<=mid)

		change(ls(p),x,v1,v2,L,mid);

	else

		change(rs(p),x,v1,v2,mid+1,R);

	s[p]=s[ls(p)]*s[rs(p)]%pp;

	o[p]=o[ls(p)]|o[rs(p)];

}

pll query(int p,int l,int r,int L=1,int R=100000)

{

	if(l<=L&&r>=R)

		return pll(s[p],o[p]);

	int mid=(L+R)>>1;

	pll s(1,0);

	if(l<=mid)

	{

		pll s1=query(ls(p),l,r,L,mid);

		s.first=s.first*s1.first%pp;

		s.second|=s1.second;

	}

	if(r>mid)

	{

		pll s2=query(rs(p),l,r,mid+1,R);

		s.first=s.first*s2.first%pp;

		s.second|=s2.second;

	}

	return s;

}

int main()

{

	freopen("d1t3.in","r",stdin);

	freopen("d1t3.out","w",stdout);

	build();

	int n;

	scanf("%d",&n);

	int i,j;

	int cnt=0;

	for(i=2;i<=281;i++)

	{

		for(j=2;j<i;j++)

			if(i%j==0)

				break;

		if(j>=i)

		{

			pri[++cnt]=i;

			a[cnt]=(i-1)*fp(i,p-2)%p;

		}

	}

	int x,y,z;

	for(i=1;i<=n;i++)

	{

		scanf("%d%d%d",&x,&y,&z);

		if(x)

		{

			ll v=0;

			for(j=1;j<=cnt;j++)

				if(z%pri[j]==0)

					v|=1ll<<(j-1);

			change(1,y,z,v);

		}

		else

		{

			pll s=query(1,y,z);

			ll ans=s.first;

			for(j=1;j<=60;j++)

				if(s.second&(1ll<<(j-1)))

					ans=ans*a[j]%p;

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

		}

	}

	return 0;

}