http://acm.hdu.edu.cn/showproblem.php?pid=5475
An easy problem
Time Limit: 8000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 755 Accepted Submission(s):
431
Problem Description
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.
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≤10^5), 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≤10^5,1≤M≤10^9)
are two integers Q and M. Q is the number of operations and M is described
above. (1≤Q≤10^5,1≤M≤10^9)
The next Q lines, each line starts with an integer x indicating the type of
operation.
operation.
if x is 1, an integer y is given, indicating the number to multiply. (0<y≤10^9)
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.)
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.
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
题目大意：t组测试数据，q个操作，每个操作（a, y）的结果X对m取余，X最初值为1，如果a==1，将X乘以y
如果a==2，将X除以第y次操作的数（即X要除的数曾出现在乘操作里）
线段树：线段树区间维护乘积，将q次操作当做q个节点，每个区间的初始值是1，乘操作（a，y）：将该次操作即该节点的数值改成其要乘的值y，
除操作（a，y）：将第y次操作即y节点的数值改成1（即可让其免去乘操作），输出从1到q区间的乘积即可
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<algorithm>
#define Lson root<<1, L, tree[root].Mid()
#define Rson root<<1|1, tree[root].Mid() + 1, R const int N = ;
typedef long long ll; struct Tree
{
ll L, R;
ll sum;
int Mid()
{
return (L + R) / ;
}
} tree[N * ]; ll a[N], m; void Push(int root)
{
tree[root].sum = (tree[root<<].sum * tree[root<<|].sum) % m;
}//维护区间乘积 void Build(int root, ll L, ll R)
{
tree[root].L = L, tree[root].R = R;
if(L == R)
{
tree[root].sum = ;
return ;
} Build(Lson);
Build(Rson); Push(root);
}//建树 void Update(int root, ll op, ll e)
{
if(tree[root].L == op && tree[root].R == op)
{
tree[root].sum = e % m;
return ;
}
if(op <= tree[root].Mid())
Update(root<<, op, e);
else
Update(root<<|, op, e);
Push(root);
}//区间单点更新 int main()
{
int t, q, op, x = ;
scanf("%d", &t);
while(t--)
{
x++;
scanf("%d%lld", &q, &m);
printf("Case #%d:\n", x);
Build(, , q);
for(int i = ; i <= q ; i++)
{
scanf("%d%lld", &op, &a[i]);
if(op == )
Update(, i, a[i]);
else
Update(, a[i], );
printf("%lld\n", tree[].sum);
}
}
return ;
}
通过用线段树的思路可以用暴力的方法来解题
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<algorithm>
#define Lson root<<1, L, tree[root].Mid()
#define Rson root<<1|1, tree[root].Mid() + 1, R const int N = ;
typedef long long ll; ll a[N], m; int main()
{
int t, op, q, x = ;
scanf("%d", &t);
while(t--)
{
x++;
ll ans = ;
scanf("%d%lld", &q, &m);
printf("Case #%d:\n", x);
for(int i = ; i <= q ; i++)
{
scanf("%d%lld", &op, &a[i]);
if(op == )
ans = ans * a[i] % m;
else
{
a[a[i]] = ;
a[i] = ;
ans = ;
for(int j = ; j < i ; j++)
ans = ans * a[j] % m;
}
printf("%lld\n", ans);
}
}
return ;
}