題干：

One day, a useless calculator was being built by Kuros. Let's assume that number X is showed on the screen of calculator. At first, X = 1. This calculator only supports two types of operation.?
1. multiply X with a number.?
2. divide X with a number which was multiplied before.?
After each operation, please output the number X modulo M.?

Input

The first line is an integer T(1≤T≤101≤T≤10), indicating the number of test cases.?
For each test case, the first line are two integers Q and M. Q is the number of operations and M is described above. (1≤Q≤105,1≤M≤1091≤Q≤105,1≤M≤109)?
The next Q lines, each line starts with an integer x indicating the type of operation.?
if x is 1, an integer y is given, indicating the number to multiply. (0<y≤1090<y≤109)?
if x is 2, an integer n is given. The calculator will divide the number which is multiplied in the nth operation. (the nth operation must be a type 1 operation.)?

It's guaranteed that in type 2 operation, there won't be two same n.?

Output

For each test case, the first line, please output "Case #x:" and x is the id of the test cases starting from 1.?
Then Q lines follow, each line please output an answer showed by the calculator.?

Sample Input

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

Sample Output

Case #1: 2 1 2 20 10 1 6 42 504 84

題目大意：

初始X=1；

給n，mod ??，表示n次操作

操作1格式 ： 1 ?b 表示用X乘上b

操作2格式： 2 ??n 表示 當(dāng)前X除掉第n次 "1操作” 的數(shù)

每次操作都要輸出一個答案，輸出的答案是要對mod取模

解題報告：

由于有除法所以我們不能每一步取模,因為對于每一個數(shù)對mod并不是都存在逆元。

考慮線段樹維護(hù)乘積，下標(biāo)代表第幾次操作，所以直接做就可以了。對于第i次操作，如果是1 b操作就是在下標(biāo)為i的地方更新為b，如果是2 n 操作就是在下標(biāo)是n的地方更新值為1，線段樹維護(hù)區(qū)間積就可以了。

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 4e5 + 5; ll mod; struct TREE {int l,r;ll val; } tr[MAX]; void pushup(int cur) {tr[cur].val = tr[cur*2].val * tr[cur*2+1].val % mod; } void build(int l,int r,int cur) {tr[cur].l = l;tr[cur].r = r;tr[cur].val = 1;if(l == r) {return;}int m = (l+r)>>1;build(l,m,cur*2);build(m+1,r,cur*2+1);pushup(cur); } void update(int tar,int cur,ll val) {if(tr[cur].l == tr[cur].r) {tr[cur].val = val;return;}if(tar <= tr[cur*2].r) update(tar,cur*2,val);else update(tar,cur*2+1,val);pushup(cur); } int main() {int t,iCase=0,op,m;ll x;cin>>t;while(t--) {scanf("%d%lld",&m,&mod);build(1,m,1);printf("Case #%d:\n",++iCase);for(int i = 1; i<=m; i++) {scanf("%d%lld",&op,&x);if(op == 1) {update(i,1,x);printf("%lld\n",tr[1].val%mod);}else {update(x,1,1);printf("%lld\n",tr[1].val%mod);}}}return 0 ; }

?

總結(jié)

以上是生活随笔為你收集整理的【HDU - 5475】An easy problem（线段树，思维）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。