题目描述
$SLON$是一个调皮的学生，为了让他静下心来，老师给他出了一道数学题：
给定表达式$A$，$A$中含有变量$x$和$+,-,*,(,)$这些符号，括号成对出现，一个算术运算符均对应两个操作数，不能出现$(-5)$或者$(4+-5)$等，乘号不能省略，并且表达式$A$中$x$只能是一阶，即一阶表达式：
合理表达式
$$A=\left\{\begin{array}{c}5 + x∗(3 + 2)\\x + 3∗x + 4∗(5 + 3∗(2 + x−2∗x))\end{array}\right.$$
不合理表达式
$$A=\left\{\begin{array}{c}5∗(3 + x∗(3 + x))\\x∗(x + x∗(1 + x))\end{array}\right..$$
求$A(mod)M==P$时，最小的 $x$.
输入
第一行输入一个表达式$A，(1≤|A|≤100000)$。
第二行输入两个整数$P (0 ≤ P ≤ M −1)、M (1 ≤ M ≤ 1000000)$。
样例一
5+3+x
9 10
样例二
20+3+x
0 5
样例三
3*(x+(x+4)*5) 1 7
输出
输出最小的非负$x$。
样例一
1
样例二
2
样例三
3
题解
一道十分经典的字符串处理四则运算题。
可以作为处理四则运算的典例。
首先，我们应该先搞清楚这个题的难点到底是什么。
其实看过题目都应该知道，
处理字符串应该是这个题的核心难点。
至于什么取模什么相等的都去死吧，我要用爆搜之剑审判你
那么，这个有四则运算在其中的字符串应该如何处理呢？
那么，这里就有了许多种处理字符串的方式：
1.保持原有中则表达式，利用栈处理字符串
2.将中则表达式转为后缀表达式，利用栈与递归处理
3.(实在不知道这种思路叫什么)将每一个数字与一个运算符绑在一起，利用递归处理字符串。
这篇文章将侧重讲解第二种方法 ~~(不然为什么把它放在最后面)~~
首先，我们来看一下这道题处理麻烦的原因：
- 括号改变计算顺序
- 字符$x$既不是运算符
- 括号前若有$'-'$，那么括号里面的所有符号(除乘号)都要进行**反转**操作
- $'*'$与$'+'('-')$一起时，应先计算乘号的内容
也就是说，如果我们把以上问题处理好，那么此题就迎刃而解了。
要解决以上问题，这里要用一种
封装思想：
这道题题目似乎很难，但是可以
浓缩为几句话
将一个四则表达式化简为$Kx+B$，且使得$$(Kx+B)modM==P$$这就是这道题的精髓。
也就是说，我们要得到的是$K$与$B$，而所谓
封装，就是将每一个括号(也不一定是括号)的$K$与$R$
装进一个$struct$或者是$pair$中，再用这个$struct$或者$pair$与其他的直接进行加、减、乘即可。(这句话十分重要，但若是不懂，看看代码应该也能理解)
剩下的，和一般的四则运算处理就差不多了。
那么我们定义：$pair$中的$first$为当前算式中$x$的系数，$second$为常数的值。
通过$pair$的两个数的定义，很容易就可以得出两个$pair$相加、减、乘时的具体操作。
为了更方便理解，这里我用数学符号进行推到(其实十分简单)
通过$pair$定义，令$pair_1=(K_1,B_1)$，$pair_2=(K_2,B_2)$.
那么$$pair_1±pair_2=(K_1x+B_1)±(K_2x+B_2)$$$$=>pair_{return}=(K_1±K_2,B_1±B_2)$$紧接着$$pair_1*pair_2=(K_1x+B_1)(K_2x+B_2)$$$$=>原式=K_1K_2x^2+(K_1+K_2)x+B_1B_2$$注意，因为题目保证这是一个一元一次的方程，那么$K_1$、$K_2$中必有一个为$0$，那么就不用考虑$x^2$了，那么$$pair_{return}=(K_1B_2+K_2B_1,B_1B_2)$$其他的操作就比较简单了。
下见代码。
1 #include<cstdio>
2 #include<stack>
3 #include<cstring>
4 #include<utility>
5 using namespace std;
6 typedef
long long LL;
7 typedef pair<LL,LL>
pll;
8 #define mp(a,b) make_pair(a,b)
9 #define ft first
10 #define sd second
11 inline LL read(){
12 #define cg (c=getchar())
13 LL x,f=
1;
char c;
14 while(cg<
'0'||
'9'<c)
if(c==
'-')f=-
1;
15 for(x=(c^
48);
'0'<=cg&&c<=
'9';x=(x<<
1)+(x<<
3)+(c^
48));
16 return x*
f;
17 #undef cg
18 }
19 const LL MAXL=
100000;
20 char str[MAXL|
1];
21 LL P,M,len;
22 pll
operator+(
const pll& a,
const pll&
b){
23 //处理两个pair相加
24 return mp((a.ft+b.ft)%M,(a.sd+b.sd)%
M);
25 }
26 pll
operator-(
const pll& a,
const pll&
b){
27 return mp((a.ft-b.ft+M)%M,(a.sd-b.sd+M)%
M);
28 }
29 pll
operator*(
const pll& a,
const pll&
b){
30 return mp((a.ft*b.sd+a.sd*b.ft)%M,a.sd*b.sd%
M);
31 }
32 bool isnum(
char c){
33 return '0'<=c&&c<=
'9';
34 }
35 stack<
char>
ch;
36 stack<pll>
sta;
37 bool cmpPrio(
char a,
char b){
38 if(a==
'('||b==
'(')
return 0;
39 if(a==
'*'||b==
'+'||b==
'-'||b==
')')
return 1;
40 return 0;
41 }
42 pll solve(pll a,pll b,
char ord){
43 if(ord==
'+')
return a+
b;
44 if(ord==
'-')
return a-
b;
45 if(ord==
'*')
return a*
b;
46 return mp(
0,
0);
47 }
48 int main(){
49 scanf(
"%s",str+
1);
50 len=strlen(str+
1);
51 P=read(),M=
read();
52 str[++len]=
')';
53 ch.push(
'(');
54 for(LL i=
1;i<=len;++
i){
55 // printf("i==%d\n",i);
56 if(str[i]==
'x')sta.push(mp(
1,
0));
57 else if(isnum(str[i])){
58 LL num=str[i]^
48;
59 while(isnum(str[i+
1]))
60 num=((num<<
1)+(num<<
3)+(str[++i]^
48))%
M;
61 sta.push(mp(
0,num));
62 }
63 else{
64 while(cmpPrio(ch.top(),str[i])){
65 pll x,y;
66 x=
sta.top();
67 sta.pop();
68 y=
sta.top();
69 sta.pop();
70 sta.push(solve(y,x,ch.top()));
71 ch.pop();
72 }
73 if(str[i]==
')')ch.pop();
74 else ch.push(str[i]);
75 }
76 }
77 pll res=
sta.top();
78 for(LL i=
0;i<=M;++i)
if((res.ft*i+res.sd)%M==
P)
79 return !printf(
"%lld\n",i);
80 return 0;
81 }
