数学计算(线段树乘法)

starletkiss 2020-05-27

数学计算(线段树乘法)

Describe

小豆现在有一个数 x,初始值为 1 。 小豆有 Q次操作,操作有两种类型:

  • 1 m: x=x×m,输出 xmodM;
  • 2 pos: x=x/ 第 pos 次操作所乘的数(保证第 pos 次操作一定为类型 1,对于每一个类型 1 的操作至多会被除一次),输出 xmodM。

Input

一共有 t 组输入。
对于每一组输入,第一行是两个数字 Q,M 。
接下来 Q 行,每一行为操作类型 op ,操作编号或所乘的数字 m (保证所有的输入都是合法的)。

Output

对于每一个操作,输出一行,包含操作执行后的 xmodM 的值

样例输入

1000000000
2
1
2
10
3
4
6
7
12
7

样例输入

2
1
2
20
10
1
6
42
504
84

Hint

对于 20% 的数据, 1≤Q≤500;
对于 100% 的数据, 1≤Q≤\(10^5\),t≤5,M≤\(10^9\).

Solution

? 1. 第一种暴力,直接乘除取模,错误,因为每次取模后得到的数,不一定能被要求的数整除,一旦不能整除就全都是0了。

? 2. 第二种是求逆元,但模数与原数不一定互质,舍去。

? 3.所以我们可以选另一种线段树的方法,定义一个全是1的数组,将每个1操作要乘的数作为数组中一个值,加线段树维护积(树的根),如果是2操作,就把数组中的对应的数(也就是积的一个因子)改为1即可,改一下树的每个节点。

? 树的节点等于左右儿子乘积取模。因此这是一道单点修改线段树的题,连建树都不用,树节点直接初始为1即可。

Code

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
ll tr[maxn<<2],mod,n;
void modi(ll rt,ll l,ll r,ll x,ll y){
	if(l==r){
		tr[rt]=y;
		return;
	}
	ll mid=(l+r)>>1;
	if(x<=mid)modi(rt<<1,l,mid,x,y);
	else modi(rt<<1|1,mid+1,r,x,y);
	tr[rt]=(tr[rt<<1]%mod)*(tr[rt<<1|1]%mod)%mod;
}
int main(){
	int t;scanf("%d",&t);
	while(t--){
		for(int i=1;i<=4e5+5;++i)tr[i]=1;
		scanf("%lld%lld",&n,&mod);
		ll x,y;
		for(ll i=1LL;i<=n;++i){
			scanf("%lld%lld",&x,&y);
			if(x==1)modi(1,1,n,i,y);
			else modi(1,1,n,y,1);
			printf("%lld\n",tr[1]);
		}
	}
	return 0;
}

相关推荐