【爆炸记】一元一次方程(slon)

待我称王封你为后i 2021-11-22 10:31 382阅读 0赞

### 文章目录 ###

*  前言
 *  题目
 *   *  题目描述
     *  输入格式
     *  输出格式
     *  样例
     *   *  样例输入1
         *  样例输出1
         *  样例输入2
         *  样例输出2
         *  样例输入3
         *  样例输出3
 *  解析
 *  Code

--------------------

# 前言 #

毫无疑问，这次考试又爆炸了QwQ，我果然还是太蒟蒻了啊

身边围绕着一群苣佬，真不好受qAq

好不容易看出来这道题怎么做了，却又不知道怎么实现。。。蓝瘦香菇

# 题目 #

## 题目描述 ##

S L O N SLON SLON是一个调皮的学生，为了让他静下心来，老师给他出了一道数学题：

给定表达式 A A A， A A A中含有变量 x x x和 \+ ,   − ,   ∗ ,   ( ,   ) +,\\ -,\\ \*,\\ (,\\ ) \+, −, ∗, (, )这些符号，括号成对出现，一个算术运算符均对应两个操作数，不能出现 ( − 5 ) (-5) (−5)或者 ( 4 + − 5 ) (4+-5) (4\+−5)等，乘号不能省略，并且表达式 A A A中 x x x只能是一阶，即一阶表达式：

合理表达式 A = 5 + x ∗ ( 3 + 2 )   o r   x + 3 ∗ x + 4 ∗ ( 5 + 3 ∗ ( 2 + x − 2 ∗ x ) ) . A=5+x∗(3 + 2)\\ or\\ x + 3∗x+4∗(5+3∗(2+x−2∗x)). A=5\+x∗(3\+2) or x\+3∗x\+4∗(5\+3∗(2\+x−2∗x)).

不合理表达式 A = 5 ∗ ( 3 + x ∗ ( 3 + x ) )   o r   x ∗ ( x + x ∗ ( 1 + x ) ) . A=5∗(3+x∗(3+x))\\ or\\ x∗(x+x∗(1+x)). A=5∗(3\+x∗(3\+x)) or x∗(x\+x∗(1\+x)).

求 A m o d &ThinSpace;&ThinSpace; M = = P A\\mod M==P AmodM==P时，最小的 x x x

## 输入格式 ##

The ﬁrst line of input contains the expression  A A A ( 1 ≤ ∣ A ∣ ≤ 100000 1 ≤|A|≤ 100000 1≤∣A∣≤100000).

The second line of input contains two integers  P P P ( 0 ≤ P ≤ M − 1 0 ≤ P ≤ M −1 0≤P≤M−1) ，  M M M ( 1 ≤ M ≤ 1000000 1 ≤ M ≤ 1000000 1≤M≤1000000).

The arithmetic expression  A A A will only consists of characters  \+ , − , ∗ , ( , ) , x +, -, \*, (, ), x \+,−,∗,(,),x and digits from  0 0 0 to  9 9 9.

The brackets will always be paired, the operators  \+ + \+,  − - − and  ∗ \* ∗ will always be applied to exactly two values (there will not be an expression  ( − 5 ) (-5) (−5) or  ( 4 + − 5 ) ) (4+-5)) (4\+−5)) and all multiplications will be explicit (there will not be an expression  4 ( 5 ) 4(5) 4(5) or  2 ( x ) ) 2(x)) 2(x)).

## 输出格式 ##

输出最小的非负 x x x

## 样例 ##

### 样例输入1 ###

5+3+x
    9 10

### 样例输出1 ###

### 样例输入2 ###

20+3+x
    0 5

### 样例输出2 ###

### 样例输入3 ###

3*(x+(x+4)*5)
    1 7

### 样例输出3 ###

# 解析 #

题目描述已经规定了 x x x的阶数为 1 1 1，也就是说它最多只能为一次方。那么这个式子一化简，就可以得到一个一元一次方程了吧。

然后令 f ( x ) = a x + b f(x) = ax + b f(x)=ax\+b，也就是这个方程，那么 f ( 0 ) f(0) f(0)就等于 b b b，还有 f ( 1 ) f(1) f(1)等于 a + b a + b a\+b，既然都得到这两个值了，也就可以*暴力*了吧 /xyx（不知道有木有人知道 Q Q QQ QQ的表情哇）

当然我在考试的时候想的是用 e x g c d exgcd exgcd求解，但是不知道为什么*玄学TLE*，炒鸡绝望有木有QwQ

当然，说是这么简单，但是实现起来就不是太简单了。首先，数据给的是中缀表达式，但是计算机无法识别，所以我们就得自己计算式子的值。

然而，我不会中缀表达式求值。。。。，所以只能转成后缀表达式求值了呢。。。

不会中缀转后缀的童鞋可以参考下[这篇博客][Link 1]，这里就不赘述了

话说学 p y t h o n python python的同学是不是就很幸福了啊，高精度三行（一行？？）代码就OK，中缀表达式求值竟然只需要一行！一行！一行！！！

print (eval (input ()))

我想转学 p y t h o n python python了QAQ

可是光中缀转后缀还不够，转完后还要计算（当然相比起来计算也就不是太难了）

总的来说，这个代码小的坑点还是比较多的，也有些细节需要考虑，洋洋洒洒算下来，我竟然用了半天加下午二十分钟才 A C AC AC，我果然是个蒟蒻QwQ

同时，大家可以从我的代码注释中看出我的艰辛心路历程：

![在这里插入图片描述][20190724205251689.PNG]  
![在这里插入图片描述][20190724205312428.PNG]

本来是用两个 s t r i n g string string来存和更改的，结果没想到 R E RE RE，结果改成 i n t int int数组后果断对了三个点，一上午都 W A   0 WA\\ 0 WA 0分的我当时那个激动啊~~~，于是再接再厉，玄学取模一加上，立马幸运之神就来了 23333 23333 23333 爱是一道光，绿的你*心旷神怡*

更详细的解释代码里面都有，可以结合着看看

# Code #

#include <cstdio>
    #include <cmath>
    #include <cstdlib>
    #include <algorithm>
    #include <vector>
    #include <set>
    #include <map>
    #include <string>
    #include <queue>
    #include <stack>
    #include <cstring>
    #include <iostream>
    using namespace std;
    #define reg register
    #define LL long long
    #define INF 0x3f3f3f3f
    #define int long long
    
    template<typename T>
    void re (T &x){ 
        x = 0;
        int f = 1;
        char c = getchar ();
        while (c < '0' || c > '9'){ 
            if (c == '-') f = -1;
            c = getchar ();
        }
        while (c >= '0' && c <= '9'){ 
            x = (x << 1) + (x << 3) + c - 48;
            c = getchar ();
        }
        x *= f;
    }
    
    template<typename T>
    void pr (T x){ 
        if (x < 0){ 
            putchar ('-');
            x = ~x + 1;
        }
        if (x / 10) pr (x / 10);
        putchar (x % 10 + 48);
    }
    
    string A;
    int p, m, a, b, lena, lenb;
    int B[100005], cnt;
    bool vis[100005];
    stack<char> S;
    
    vector<int>pos;
    
    int cmp (char s){ 
        if (s == '(')
            return 0;
        else if (s == '+' || s == '-')
            return 1;
        else return 2;
    }
    
    int fix (int x){     //神仙取模 OTZ %%%
        return (x % m + m) % m;
    }
    
    void transfer (string A){ 
        lena = A.length ();
        for (int i = 0; i < lena; i++){ 
            if (A[i] >= '0' && A[i] <= '9'){     //原本是直接“截取”到B中，但是下面有讲坏处，所以改为整形+打标
                                                //双重判定是数字还是x还是运算符
                /*int j; for (j = i; j < lena && A[j] >= '0' && A[j] <= '9'; j++) B += A[j]; B += ' '; i = j - 1;*/
                if (i != 0 && A[i - 1] >= '0' && A[i + 1] <= '9'){ 
                    B[cnt] = fix (B[cnt] * 10 + A[i] - 48);
                }
                else B[++cnt] = A[i] - 48;
            }
            else if (A[i] == 'x'){ 
                /*B += A[i]; B += ' ';*/
                B[++cnt] = A[i];
                vis[cnt] = 1;    //打标
            }
            else if (A[i] == '(')
                S.push (A[i]);  //是左括号的话直接放栈，遇到右括号再处理
            else if (A[i] == '+' || A[i] == '-' || A[i] == '*'){ 
                if (S.empty ()){     //如果说栈里没有的话就直接放（蒟蒻在这都调了五分钟。。）
                    S.push (A[i]);
                    continue;
                }
                char c1 = A[i], c2 = S.top ();  //判断优先级，左括号最低，加减次之，乘最高
                int lev1 = cmp (A[i]), lev2 = cmp (S.top ());
                if (lev1 > lev2) S.push (A[i]); //要维持一个栈中优先级递增的序列，因为可能后面有比他更高或相等的
                                                //所以到下一个运算符时在判断前一个可不可以输出
                else{ 
                    //如果说栈里的都比他大或等于，就说明前面的优先输出，一直到小于才放进去
                    while (!S.empty () && lev1 <= cmp (S.top ())){ 
                        /*B += S.top (); B += ' ';*/
                        B[++cnt] = S.top ();
                        vis[cnt] = 1;
                        S.pop ();
                        /*if (!S.empty ()) lev2 = cmp (S.top ());*/
                    }
                    S.push (A[i]);
                }
            }
            else{ 
                while (S.top () != '('){     //如果说遇到右括号，那么这个括号里的内容都输完了，可以直接全部输到B里了
                    /*B += S.top (); B += ' ';*/
                    B[++cnt] = S.top ();
                    vis[cnt] = 1;
                    S.pop ();
                }
                S.pop ();   //把左括号也输出去
            }
        }
        while (!S.empty ()){     //如果说这一串都输完了，和上同理
            /*B += S.top (); B += ' ';*/
            B[++cnt] = S.top ();
            vis[cnt] = 1;
            S.pop ();
        }
    }
    
    void solve (int x){ 
        /*for (int i = 0; i < pos.size (); i++) B[pos[i]] = x + '0';*/
        //cout << B << endl;
        stack<int> S2;
        for (int i = 1; i <= cnt; i++){ 
            if (!vis[i]){    //vis为零，说明数字
                /*int j, num = 0; for (j = i; j < lenb && B[j] >= '0' && B[j] <= '9'; j++) num = ((num << 1) % m + (num << 3) % m + B[j] - '0') % m; i = j - 1;*/
                S2.push (B[i]);
            }
            //else if (B[i] == ' ') continue;
            else if (B[i] == 'x'){   // !vis上面判完了，下面都是符号或x
                S2.push (x);
            }
            else{ 
                int xx = S2.top (); S2.pop ();
                int yy = S2.top (); S2.pop ();
                switch (B[i]){ 
                    case '+': S2.push (fix (xx + yy)); break;
                    case '-': S2.push (fix (yy - xx + m)); break;   //这里坑了我最久，如果说是减，被减数先放进去，在后面
                                                                    //而且减法先加再膜怕负数
                    case '*': S2.push (fix (1ll * xx * yy)); break;
                }
            }
        }
        if (x == 0) b = S2.top ();
        else a = S2.top () - b;
    }
    
    signed main (){  //这道题主要是神仙取模，不知为何一取就对。。。
        cin >> A;
        //re (p); re (m);
        cin >> p >> m;
        transfer (A);   //因为A是中缀表达式，所以把它转为后缀（中缀不会只能后缀QwQ）
        //cout << B << endl;
        //lenb = B.length (); //本来开始是用的string来存，但是有坏处，如果不加分割可能会将两个数读成一个数
        /*for (int i = 0; i < lenb; i++) //但是这样做会爆栈（猜的RE） if (B[i] == 'x') pos.push_back (i);*/
        solve (0);  //令f(x) = ax + b，则f(0) = b, f(1) = a + b，可以借此算出两个数，暴力找解
        solve (1);
        for (int i = 0; i < m; i++)
            if (fix (a * i + b) == p){ 
                //pr (i);
                //putchar (10);
                cout << i << endl;
                return 0;
            }
        return 0;
    }

但是为什么 e x g c d exgcd exgcd会 T T T两个点呢？？

大神求解QAQ，请神犇在评论区留言谢谢 /bq

LL exgcd (LL a, LL b, LL &x, LL &y){ 
        if (!b){ 
            x = 1, y = 0;
            return a;
        }
        LL r = exgcd (b, a % b, y, x);
        y -= x * (a / b);
        return r;
    }
    
    
    int main (){ 
        LL gcd = exgcd (a, m, x, y);
        x = x * (p - b) / gcd;
        //cout << fix (x) << endl;
        while (x < 0) x += m / gcd;
        while (x >= 0){ 
            if (x - (m / gcd) >= 0)
                x -= m / gcd;
            else break;
        }
        cout << x << endl;
    }

[Link 1]: https://blog.csdn.net/weixin_43925239/article/details/97136338
[20190724205251689.PNG]: /images/20211122/3a366226070840d8a2af330d1fe09cce.png
[20190724205312428.PNG]: /images/20211122/879a01147bce4092a8a9fcce921e4465.png