数学计算(线段树乘法)
数学计算(线段树乘法)
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; }
相关推荐
starletkiss 2020-05-26
Dyancsdn 2020-07-28
baike 2020-07-04
henryzhihua 2020-06-10
lickylin 2020-04-08
wellfly 2020-03-08
waitwolf 2019-12-19
kuoying 2019-11-12
kuoying 2019-11-05
范范 2019-11-03
kuoying 2019-11-02
seekerhit 2019-10-19
lickylin 2019-06-28
木易电影 2018-05-17
玲珑 2018-03-04
玲珑 2018-02-12
安在信息安全新媒体 2018-01-13
美国教育漫谈bgu 2017-12-28