【题解】[TJOI 2018] 数学计算（线段树）

本文主要是介绍【题解】[TJOI 2018] 数学计算（线段树），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题面

【题目描述】
小豆现在有一个数$x$，初始值为$1$. 小豆有$Q$次操作，操作有两种类型:
$1$ $m:$ $x=x\ast m$ ，输出 $x$%$mod$;
$2$ $pos:$ $x=x$ / 第$pos$次操作所乘的数（保证第$pos$次操作一定为类型$1$，对于每一个类型$1$的操作至多会被除一次），输出$x$ % $mod$
【输入】
一共有$t$组输入（$t\le 5$）
对于每一组输入，第一行是两个数字$Q,mod$($Q\le 100000,mod\le 1000000000$);
接下来$Q$行，每一行为操作类型$op$，操作编号或所乘的数字$m$（保证所有的输入都是合法的）.
$1\le Q\le 100000$
【输出】
对于每一个操作，输出一行，包含操作执行后的$x$%$mod$的值
【样例输入】

1 
10 1000000000 
1 2 
2 1 
1 2 
1 10 
2 3 
2 4 
1 6 
1 7 
1 12 
2 7

【样例输出】

2 
1 
2 
20 
10 
1 
6 
42 
504 
84

算法分析

隐藏的线段树。
纯模拟肯定不行，long long也存不下，只有高精度。需要注意，题目要求输出时取模，但是求解的时候不取模，如果一边取模一边计算就会出现取模为0后，乘以任何 数都是0。
因为除法除的数都是乘过的数，那么其实可以只看乘法。例如除以第k次的乘数s，可以看作第k次乘以了1。这样，我们就将整个操作全部变成了乘法。题目就变成了，每次乘以一个数，输出结果取模。
我们需要将这些乘数都保存下了，同时要进行修改，就使用线段树。
构造一个1~n的全为1的序列A。第k次乘以数s，就将序列A[k]=s，第k次处于第t次的乘数，就将A[t]=1。
就是线段树的一个单点修改。最后的答案就是线段树的根节点S[1]，包含了所有乘数的和。

参考程序

#include <bits/stdc++.h>
using namespace std;
int n,m,T;
long long s[500010];
void built(int k,int l,int r)	//所有结点初始化为1 
{s[k]=1;if(l==r) return;int mid=(l+r)/2;built(k*2,l,mid);built(k*2+1,mid+1,r);
}
void change(int k,int l,int r,int x,int v)
{if(l==r&&x==l){s[k]=v;return;}int mid=(l+r)/2;if(l<=x&&x<=mid) change(k*2,l,mid,x,v);if(mid+1<=x&&x<=r) change(k*2+1,mid+1,r,x,v);s[k]=((s[k*2]%m)*(s[k*2+1]%m))%m;
}
int main()
{scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);built(1,1,n);	//建立一个1~n的序列，全部为1，表示第i次乘的数 int x,y;for(int i=1;i<=n;i++){scanf("%d%d",&x,&y);if(x==1) change(1,1,n,i,y);	//第i次乘以y else change(1,1,n,y,1);	//除以第y次的乘数，即将其乘数变为1 printf("%lld\n",s[1]);//s[1]就是1~i所有乘数的乘积 }} return 0;
}

这篇关于【题解】[TJOI 2018] 数学计算（线段树）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---