首页 > ACM题库 > HDU-杭电 > hdu 2685 I won’t tell you this is about number theory-递归和分治-[解题报告]C++
2014
02-13

hdu 2685 I won’t tell you this is about number theory-递归和分治-[解题报告]C++

I won’t tell you this is about number theory

问题描述 :

To think of a beautiful problem description is so hard for me that let’s just drop them off. :)
Given four integers a,m,n,k,and S = gcd(a^m-1,a^n-1)%k,calculate the S.

输入:

The first line contain a t,then t cases followed.
Each case contain four integers a,m,n,k(1<=a,m,n,k<=10000).

输出:

The first line contain a t,then t cases followed.
Each case contain four integers a,m,n,k(1<=a,m,n,k<=10000).

样例输入:

1
1 1 1 1

样例输出:

0

#include <cstdio>
#include <algorithm>
using namespace std;
struct node{
	int l,r,cl;
	bool lz;
}t[300009];
void build(int st,int ed,int cr){
	t[cr].r=ed;
	t[cr].l=st;
	t[cr].cl=2;
	t[cr].lz=1;
	if(st==ed)
		return ;
	build(st,(st+ed)/2,2*cr);
	build((st+ed)/2+1,ed,cr*2+1);
	return ;
}
void insert(int st,int ed,int cr,int incl){
	if(t[cr].r==ed&&t[cr].l==st){
		t[cr].cl=(1<<incl);
		t[cr].lz=1;
		return ;//不用再递归了,这样子已经足够了
	}
	if(t[cr].lz){
		t[cr].lz=0;//插入的不是当前线段,而是子线段,那么把这个线段破开。并把这个点信息给子线段
		t[cr*2+1].cl=t[cr*2].cl=t[cr].cl;
		t[cr*2+1].lz=t[cr*2].lz=1;
	}
	int mid=(t[cr].r+t[cr].l)>>1;
	if(ed<=mid){
		insert(st,ed,2*cr,incl);
	}else if(st>mid){
		insert(st,ed,2*cr+1,incl);
	}else{
		insert(st,mid,2*cr,incl);
		insert(mid+1,ed,2*cr+1,incl);
	}
	t[cr].cl=t[cr*2].cl|t[cr*2+1].cl;
	return ;
}
int query(int st,int ed,int cr){
	if((t[cr].lz)||(t[cr].r==ed&&t[cr].l==st)){
		return t[cr].cl;
	}
	int mid=(t[cr].l+t[cr].r)>>1;
	if(ed<=mid){
		return query(st,ed,cr*2);
	}else if(st>mid){
		return query(st,ed,cr*2+1);
	}else{
		return query(st,mid,cr*2)|query(mid+1,ed,cr*2+1);
	}
}
int main(){
	int L,T,O,A,B,C,ret,ans;
	char op;
	while(scanf("%d%d%d",&L,&T,&O)==3){
		build(1,L,1);
		while(O--&&scanf(" %c",&op)){
			if(op=='C'){
				scanf("%d%d%d",&A,&B,&C);
				if(A>B)swap(A,B);
				insert(A,B,1,C);
			}else{
				scanf("%d%d",&A,&B);
				if(A>B)swap(A,B);
				ret=query(A,B,1);
				ans=0;
				for(int i=0;i<32;i++)
					if(ret&(1<<i))
						ans++;
				printf("%d\n",ans);
			}
		}
	}
}

解题转自:http://blog.csdn.net/u010028230/article/details/9034135