starletkiss 2020-05-27
小豆现在有一个数 x,初始值为 1 。 小豆有 Q次操作,操作有两种类型:
1 m
: x=x×m,输出 xmodM;2 pos
: x=x/ 第 pos 次操作所乘的数(保证第 pos 次操作一定为类型 1,对于每一个类型 1 的操作至多会被除一次),输出 xmodM。一共有 t 组输入。
对于每一组输入,第一行是两个数字 Q,M 。
接下来 Q 行,每一行为操作类型 op ,操作编号或所乘的数字 m (保证所有的输入都是合法的)。
对于每一个操作,输出一行,包含操作执行后的 xmodM 的值
1000000000 2 1 2 10 3 4 6 7 12 7
2 1 2 20 10 1 6 42 504 84
对于 20% 的数据, 1≤Q≤500;
对于 100% 的数据, 1≤Q≤\(10^5\),t≤5,M≤\(10^9\).
? 1. 第一种暴力,直接乘除取模,错误,因为每次取模后得到的数,不一定能被要求的数整除,一旦不能整除就全都是0了。
? 2. 第二种是求逆元,但模数与原数不一定互质,舍去。
? 3.所以我们可以选另一种线段树的方法,定义一个全是1的数组,将每个1操作要乘的数作为数组中一个值,加线段树维护积(树的根),如果是2操作,就把数组中的对应的数(也就是积的一个因子)改为1即可,改一下树的每个节点。
? 树的节点等于左右儿子乘积取模。因此这是一道单点修改线段树的题,连建树都不用,树节点直接初始为1即可。
#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; }