異議あり！

纪念我学会

模板自存：

1、快速幂

ll power(ll a,ll p){
	ll sum=1;
	while(p){
		if(p%2==1) sum=(sum*a)%mod;
		p/=2;
		a=(a*a)%mod;
	}
	return sum%mod;
}

2、乘法逆元

int exgcd(int a,int b,int &x,int &y){
	if(b==0){
		x=1; y=0; //当kx+0y=gcd(a,b)时的根解
		return a;
	}
	int d=exgcd(b,a%b,x,y);
	int tmp=y;
	y=x-(a/b)*y;
	x=tmp;
	return d;
}
int inverse(int a,int b,int c){//三个参数，含义：ax%b=c，当c=1时即可求出a的逆元，遇到k/a%mod，直接用k*x%mod等效替代
	int x,y;//一对解
	int d=exgcd(a,b,x,y);//d为a和b的最大公因数，x和y是一组特解
	if(c%d!=0){//c不是d的倍数
			//无解
	}else{
			x*=c/d;
			y*=c/d; //将ax+by=gcd(a,b)的解转化成ax+by=c (d|c(d是c的因数))的特解
			x=(x%(b/d)+(b/d))%(b/d);//求出最小的一组通解，x即为a在模b意义上的乘法逆元
			//目的：求出通解
			//已知通解形如：ax+ak + by*bf = c
			//∵k、f应为整数
			//∴ak应为b的倍数，表示为b|ak
			//同时除以d，(b/d)|(a/d)k
			//∵d是a、b的最小公因数
			//∴(b/d)与(a/d)互质
			//∴想要实现(b/d)|(a/d)k，必须实现(b/d)|k，即k是(b/d)的倍数即可
			//通解：x = 特解+k = 特解+（b/d)m (m∈自然数集)
			return x;
	}
}

3、欧拉筛

bool nap[30000010];//not a pirme
vector<int>pri;
int eul[30000010];//eul[i]为1~i中与i互质的数的个数 
void elp(int n){
	nap[1]=true;
	for(int i=2;i<=n;i++){
		if(!nap[i]){
			pri.push_back(i);
			eul[i]=i-1;//对于质数i，φ(i)=i-1，即1~i-1的所有数都与i互质
		}
		for(int j=0;j<pri.size()&&i*pri[j]<=n;j++){
			nap[pri[j]*i]=true;
			if(i%pri[j]==0){
				eul[pri[j]*i]=pri[j]*eul[i];
				break;
			}
			else eul[pri[j]*i]=(pri[j]-1)*eul[i];
		}
	}
}

4、线段树

int n;
int a[100010],tree[400010];//数学方法可以证明，对于区间[1,n]，最深的节点编号不会超过4*n
int lazytag[100010];//懒惰标记，存储加法
void pushdown(int v,int l,int r){//下发一层懒惰标记
	lazytag[v*2]+=lazytag[v];//将懒惰标记发放给左子树
	lazytag[v*2+1]+=lazytag[v];//将懒惰标记发放给右子树
	int mid=(l+r)>>1;
	tree[v*2]+=lazytag[v]*(mid-l+1);//将增加量给予左子树
	tree[v*2+1]+=lazytag[v]*(r-mid);//将增加量给予右子树
	lazytag[v]=0;//清空当前层的懒惰标记
}
void build(int v,int l,int r){ //建树过程，v表示节点编号，l、r表示区间，调用函数时填写根节点信息，即build(1,1,n);
	if(l==r){ //叶子节点
		tree[v]=a[l];//区间中只有l一个元素
		return;
	}
	int mid=(l+r)>>1;
	build(v*2,l,mid);//构建左儿子
	build(v*2+1,mid+1,r);//构建右儿子
	tree[v]=tree[v*2]+tree[v*2+1];//该区间的值为左右儿子值之和
}
void modify(int v,int l,int r,int x,int y){ //单点修改，将a[x]修改为y，v表示节点编号，l、r表示区间，调用函数时填写根节点信息，即modify(1,1,n,x,y);
	if(l==r){
		tree[v]=y;//更改叶子节点的值
		return;
	}
	int mid=(l+r)>>1;//下一层子树的区间中值
	if(x<=mid){ //要修改的编号x在左子树的区间中，说明需要递归至左子树
		modify(v*2,l,mid,x,y);//递归到下一层的左子树
	}else{ //要修改的编号x在右子树的区间中，说明需要递归至右子树
		modify(v*2+1,mid+1,r,x,y);//递归到下一层的右子树
	}
	tree[v]=tree[v*2]+tree[v*2+1];//重新回溯赋值
}
void modify(int v,int l,int r,int L,int R,int y){ //区间修改，将[L,R]增加y
	if(r<L||R<l){ //交是空的
		return;
	}
	if(L<=l&&r<=R){ //[l,r]被包含在[L,R]中
		lazytag[v]+=y;//在v处的懒惰标记增加y
		tree[v]+=y*(r-l+1);//在v处的tree增加子孙的变化值
		return;
	}
	pushdown(v,l,r);//如果此层不满足条件，需将懒惰标记向下发放一层，在下一层中进行标记
	int mid=(l+r)>>1;//下一层子树的区间中值
	modify(v*2,l,mid,L,R,y);//下发至左子树进行修改尝试
	modify(v*2+1,mid+1,r,L,R,y);//下发至右子树进行修改尝试
	tree[v]=tree[v*2]+tree[v*2+1];//重新回溯赋值
}
int ask(int v,int l,int r,int L,int R){ //区间求和，求区间[L,R]的和，v表示节点编号，l、r表示区间，调用函数时填写根节点信息，即ask(1,1,n,L,R);
	//[l,r] [L,R]的交的和
	if(r<L||R<l){ //交是空的
		return 0;
	}
	if(L<=l&&r<=R){ //[l,r]被包含在[L,R]中
		return tree[v];//返回交集中的元素和
	}
	pushdown(v,l,r);
	int mid=(l+r)>>1;
	return ask(v*2,l,mid,L,R)+ask(v*2+1,mid+1,r,L,R);//递归至左右子树的和
}