bzoj 3813: 奇数国 （线段树+质因数分解+线性筛+线性逆元）

Description

Input

Output

Sample Input

Sample Output

HINT

x≤100000，当ai=0时0≤ci−bi≤100000

Source

2015年国家集训队测试

题解：线段树+质因数分解+线性筛+线性逆元

对于所有位置的数质因数分解，然后维护区间中质因数的出现次数。

number*x+product*y=1 => number*x=1 (mod product) 

同余方程有解，当且仅当number,product互质。

所有我们要求的就是[1,product]中与product互质的数的个数，即phi(product)

然后利用公式求解即可。

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<cmath>#define N 100003#define p 19961993#define LL long longusing namespace std;LL mp[303],pd[303],prime[303],inv[303];struct data {	int cnt[63];	data() {		memset(cnt,0,sizeof(cnt));	}}tr[N*4];int n;void init(){	for (int i=2;i<=300;i++) {		if (!pd[i]) prime[++prime[0]]=i,mp[i]=prime[0];		for (int j=1;j<=prime[0];j++) {			if (prime[j]*i>300) break;			pd[prime[j]*i]=1;			if (i%prime[j]==0) break;		}	}	prime[0]=60;	inv[0]=inv[1]=1;	for (int i=2;i<=281;i++) 	 inv[i]=(p-p/i)*inv[p%i]%p;	//for (int i=2;i<=261;i++) cout<<inv[i]<<" ";	//cout<<endl;}void update(int now){	for (int i=1;i<=60;i++) tr[now].cnt[i]=tr[now<<1].cnt[i]+tr[now<<1|1].cnt[i];}void build(int now,int l,int r){	if (l==r) {		memset(tr[now].cnt,0,sizeof(tr[now].cnt));		tr[now].cnt[2]=1;		return;	}	int mid=(l+r)/2;	build(now<<1,l,mid);	build(now<<1|1,mid+1,r);	update(now);}void add(data &a,data b){	for (int i=1;i<=60;i++)	 a.cnt[i]+=b.cnt[i];}data query(int now,int l,int r,int ll,int rr){	if (ll<=l&&r<=rr) return tr[now];	int mid=(l+r)/2; data a; 	if (ll<=mid) add(a,query(now<<1,l,mid,ll,rr));	if (rr>mid) add(a,query(now<<1|1,mid+1,r,ll,rr));	return a;}void pointchange(int now,int l,int r,int x,int val){	if (l==r) {		memset(tr[now].cnt,0,sizeof(tr[now].cnt));		int k=val;		for (int i=1;prime[i]*prime[i]<=k;i++) 		 if (k%prime[i]==0) {		 	while (k%prime[i]==0) k/=prime[i],tr[now].cnt[i]++;		 }		if (k>1) tr[now].cnt[mp[k]]++;		return;	}	int mid=(l+r)/2;	if (x<=mid) pointchange(now<<1,l,mid,x,val);	else pointchange(now<<1|1,mid+1,r,x,val);	update(now);}LL quickpow(LL num,int x){	LL base=num%p; LL ans=1;	while (x) {		if (x&1) ans=ans*base%p;		x>>=1;		base=base*base%p;	}	return ans;}int main(){	freopen("a.in","r",stdin);	freopen("my.out","w",stdout);	init(); int T;	scanf("%d",&T); n=100000;	build(1,1,n);	for (int i=1;i<=T;i++) {		int opt,x,y;		scanf("%d%d%d",&opt,&x,&y);		if (opt==0) {		  data a=query(1,1,n,x,y);		  LL ans=1;		  for (int j=1;j<=60;j++)		   if (a.cnt[j]) 		    ans=ans*quickpow(prime[j],a.cnt[j])%p*(LL)(prime[j]-1)%p*inv[prime[j]]%p;		    //cout<<quickpow(prime[j],a.cnt[j])%p<<" "<<inv[prime[j]]<<endl;		  printf("%I64d/n",ans%p);	    }	    else pointchange(1,1,n,x,y);	}}