Submission #1292176

#	Time	Username	Problem	Language	Result	Execution time	Memory
1292176		cnam9	Slon (COCI15_slon)	C++20	120 / 120	2 ms	1084 KiB

slon

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

constexpr int N = 1e5 + 5;

int mod;

struct Token {
    int a;
    int b;

    inline bool operator==(const Token &other) const = default;

    inline void operator+=(const Token &other) {
        a += other.a;
        a -= a >= mod ? mod : 0;
        b += other.b;
        b -= b >= mod ? mod : 0;
    }

    inline void operator-=(const Token &other) {
        a -= other.a;
        a += mod & (a >> 31);
        b -= other.b;
        b += mod & (b >> 31);
    }

    inline void operator*=(const Token &other) {
        a = ((long long) a * other.b + (long long) b * other.a) % mod;
        b = (long long) b * other.b % mod;
    }
};

constexpr Token X = {1, 0};
constexpr Token ADD = {-1, 1};
constexpr Token SUB = {-1, 2};
constexpr Token MUL = {-1, 3};
constexpr Token OPEN = {-1, 4};
constexpr Token CLOSE = {-1, 5};
Token charToToken[128];

Token tokens[N];
int nTokens;

int pointer;

Token evaluate() {
    vector<Token> myTokens;
    while (true) {
        Token token = tokens[pointer++];

        if (token == OPEN) {
            myTokens.push_back(evaluate());
            continue;
        }
        if (token == CLOSE) {
            break;
        }
        myTokens.push_back(token);
    }

    vector<Token> newTokens;
    bool multiplying = false;

    for (Token token : myTokens) {
        if (token == MUL) {
            multiplying = true;
        } else if (token == ADD || token == SUB) {
            multiplying = false;
            newTokens.push_back(token);
        } else if (multiplying) {
            newTokens.back() *= token;
        } else {
            newTokens.push_back(token);
        }
    }

    Token result = newTokens.front();

    for (int i = 1; i < newTokens.size(); i += 2) {
        if (newTokens[i] == ADD) {
            result += newTokens[i + 1];
        } else {
            result -= newTokens[i + 1];
        }
    }
    return result;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    // freopen("input.txt", "r", stdin);

    string expression;
    cin >> expression;

    int value;
    cin >> value >> mod;

    nTokens = 0;

    charToToken['x'] = X;
    charToToken['+'] = ADD;
    charToToken['-'] = SUB;
    charToToken['*'] = MUL;
    charToToken['('] = OPEN;
    charToToken[')'] = CLOSE;

    bool is_num = false;
    int num = 0;
    for (char c : expression) {
        if (isdigit(c)) {
            if (is_num) {
                num = (num * 10 + c - '0') % mod;
            } else {
                is_num = true;
                num = c - '0';
            }
        } else {
            if (is_num) {
                is_num = false;
                tokens[nTokens++] = {0, num};
            }
            tokens[nTokens++] = charToToken[c];
        }
    }
    if (is_num) {
        tokens[nTokens++] = {0, num};
    }
    tokens[nTokens] = CLOSE;

    pointer = 0;
    Token root = evaluate();

    int a = root.a;
    int b = (value - root.b + mod) % mod;

    int d = __gcd(__gcd(a, b), mod);
    a /= d;
    b /= d;
    mod /= d;

    int phi = 1;
    int n = mod;

    for (int p = 2; p * p <= n; p++) {
        if (n % p) continue;
        n /= p;
        phi *= p - 1;

        while (n % p == 0) {
            n /= p;
            phi *= p;
        }
    }
    if (n > 1) {
        phi *= n - 1;
    }

    // b * a ^ (phi - 1) mod m
    int res = b;
    for (int k = phi - 1; k; k >>= 1) {
        if (k & 1)
            res = (long long) res * a % mod;
        a = (long long) a * a % mod;
    }
    cout << res;

    return 0;
}

• Subtask 1: 120 / 120