test/AOJ/0264-Finite-Field-Calculator.test.cpp

View this file on GitHub
Last update: 2020-10-10 20:15:48+09:00
Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0264&lang=ja#

Depends on

Mod-Int (コンパイル時mod型と実行時mod型) (Math/Modulo/mod-int.hpp)

Code

#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0264&lang=ja#"
#include <cassert>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <sstream>
#include <stdexcept>

#include "../../Math/Modulo/mod-int.hpp"

using namespace std;
using Mint = DynamicModInt<0>;
using Itr = string::const_iterator;

Mint expr(Itr&);
Mint term(Itr&);
Mint factor(Itr&);
Mint number(Itr&);

Mint expr(Itr& p) {
    Mint res = term(p);
    while (*p == '+' || *p == '-') {
        if (*p == '+') {
            res += term(++p);
        } else {
            res -= term(++p);
        }
    }
    return res;
}

Mint term(Itr& p) {
    Mint res = factor(p);
    while (*p == '*' || *p == '/') {
        if (*p == '*') {
            res *= factor(++p);
        } else {
            const auto v = factor(++p);
            if (v == 0) throw std::runtime_error("Divide by zero");
            res /= v;
        }
    }
    return res;
}

Mint factor(Itr& p) {
    if (*p == '(') {
        const auto res = expr(++p);
        assert(*p == ')');
        ++p;
        return res;
    }
    assert(isdigit(*p));
    return number(p);
}

Mint number(Itr& p) {
    int res = 0;
    while (isdigit(*p)) {
        res = res * 10 + (*p - '0');
        ++p;
    }
    return Mint::raw(res);
}

string removeSpace(const char* s) {
    string res;
    res.reserve(100010);

    istringstream iss(s);
    string part;
    while (iss >> part) res += move(part);

    return res;
}

int main() {
    static char line[100100];

    int p;
    while (scanf(" %d :", &p), p) {
        Mint::setMod(p);

        fgets(line, sizeof(line), stdin);
        const string s = removeSpace(line);

        try {
            Itr itr = s.cbegin();
            auto ans = expr(itr);
            printf("%s = %d (mod %ld)\n", s.c_str(), int(ans), Mint::mod());
        } catch (const std::runtime_error& e) {
            puts("NG");
        }
    }

    return 0;
}

#line 1 "test/AOJ/0264-Finite-Field-Calculator.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0264&lang=ja#"
#include <cassert>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <sstream>
#include <stdexcept>

#line 2 "Math/Modulo/mod-int.hpp"
#include <cstdint>
#line 4 "Math/Modulo/mod-int.hpp"
#include <iostream>
#include <limits>

/**
 * @brief Mod-Int (コンパイル時mod型と実行時mod型)
 */
namespace internal {

template <class ModHolder>
class ModInt {
private:
    int64_t value;

public:
    constexpr ModInt() noexcept
        : value(0) {}

    constexpr ModInt(int64_t v) noexcept
        : value(ModInt::normalized(v)) {}

    static constexpr const ModInt raw(int64_t v) noexcept {
        ModInt ret;
        ret.value = v;
        return ret;
    }

    static constexpr ModInt nullopt() noexcept { return ModInt::raw(std::numeric_limits<int64_t>::min()); }

    constexpr bool isNull() const noexcept { return *this == ModInt::nullopt(); }

    static constexpr int64_t mod() { return ModHolder::mod; }

    static int64_t setMod(int64_t m) noexcept {
        assert(m >= 1);
        return ModHolder::mod = m;
    }

    template <class T>
    constexpr explicit operator T() const noexcept {
        return static_cast<T>(value);
    }

    constexpr int64_t val() const noexcept { return value; }

    constexpr ModInt& operator+=(const ModInt& rhs) noexcept {
        if ((value += rhs.value) >= mod()) value -= mod();
        return *this;
    }
    constexpr ModInt& operator-=(const ModInt& rhs) noexcept {
        if ((value -= rhs.value) < 0) value += mod();
        return *this;
    }
    constexpr ModInt& operator*=(const ModInt& rhs) noexcept {
        (value *= rhs.value) %= mod();
        return *this;
    }
    constexpr ModInt& operator/=(const ModInt& rhs) noexcept { return *this *= rhs.inv(); }
    constexpr const ModInt inv() const noexcept { return ModInt(ModInt::inverse(value, mod())); }
    constexpr const ModInt operator+() const noexcept { return *this; }
    constexpr const ModInt operator-() const noexcept { return ModInt(-value); }

    constexpr const ModInt pow(int64_t expv) const noexcept {
        int64_t ret = 1, square = value;
        for (uint64_t p = std::abs(expv); p; p >>= 1) {
            if (p & 1) (ret *= square) %= mod();
            (square *= square) %= mod();
        }
        return (expv < 0) ? (ModInt::raw(1) / ModInt::raw(ret)) : ModInt::raw(ret);
    }

    friend constexpr bool operator==(const ModInt& lhs, const ModInt& rhs) noexcept { return lhs.value == rhs.value; }
    friend constexpr bool operator!=(const ModInt& lhs, const ModInt& rhs) noexcept { return lhs.value != rhs.value; }
    friend constexpr const ModInt operator+(const ModInt& lhs, const ModInt& rhs) noexcept { return ModInt(lhs) += rhs; }
    friend constexpr const ModInt operator-(const ModInt& lhs, const ModInt& rhs) noexcept { return ModInt(lhs) -= rhs; }
    friend constexpr const ModInt operator*(const ModInt& lhs, const ModInt& rhs) noexcept { return ModInt(lhs) *= rhs; }
    friend constexpr const ModInt operator/(const ModInt& lhs, const ModInt& rhs) noexcept { return ModInt(lhs) /= rhs; }

    friend std::ostream& operator<<(std::ostream& os, const ModInt& x) {
#ifdef LOCAL_DEBUG
        if (x.isNull()) return os << "{nullopt}";
#endif
        return os << x.value;
    }

    friend std::istream& operator>>(std::istream& is, ModInt& x) {
        is >> x.value;
        x.value = ModInt::normalized(x.value);
        return is;
    }

private:
    static constexpr int64_t normalized(int64_t n) {
        n = (-mod() <= n && n < mod() ? n : n % mod());
        if (n < 0) n += mod();
        return n;
    }

    static constexpr int64_t inverse(int64_t a, int64_t m) {
        int64_t u = 0, v = 1;
        while (a != 0) {
            const auto t = m / a;
            static_cast<void>(m -= t * a), std::swap(m, a);
            static_cast<void>(u -= t * v), std::swap(u, v);
        }
        assert(m == 1);
        return u;
    }
};

template <int64_t Mod>
struct StaticModHolder {
    static constexpr int64_t mod = Mod;
};

template <int ID>
struct DynamicModHolder {
    static int64_t mod;
};
template <int ID>
int64_t DynamicModHolder<ID>::mod;

}  // namespace internal

template <int64_t Mod>
using StaticModInt = internal::ModInt<internal::StaticModHolder<Mod>>;

using ModInt1000000007 = StaticModInt<int(1e9) + 7>;
using ModInt998244353 = StaticModInt<998244353>;

template <int ID>
using DynamicModInt = internal::ModInt<internal::DynamicModHolder<ID>>;
#line 11 "test/AOJ/0264-Finite-Field-Calculator.test.cpp"

using namespace std;
using Mint = DynamicModInt<0>;
using Itr = string::const_iterator;

Mint expr(Itr&);
Mint term(Itr&);
Mint factor(Itr&);
Mint number(Itr&);

Mint expr(Itr& p) {
    Mint res = term(p);
    while (*p == '+' || *p == '-') {
        if (*p == '+') {
            res += term(++p);
        } else {
            res -= term(++p);
        }
    }
    return res;
}

Mint term(Itr& p) {
    Mint res = factor(p);
    while (*p == '*' || *p == '/') {
        if (*p == '*') {
            res *= factor(++p);
        } else {
            const auto v = factor(++p);
            if (v == 0) throw std::runtime_error("Divide by zero");
            res /= v;
        }
    }
    return res;
}

Mint factor(Itr& p) {
    if (*p == '(') {
        const auto res = expr(++p);
        assert(*p == ')');
        ++p;
        return res;
    }
    assert(isdigit(*p));
    return number(p);
}

Mint number(Itr& p) {
    int res = 0;
    while (isdigit(*p)) {
        res = res * 10 + (*p - '0');
        ++p;
    }
    return Mint::raw(res);
}

string removeSpace(const char* s) {
    string res;
    res.reserve(100010);

    istringstream iss(s);
    string part;
    while (iss >> part) res += move(part);

    return res;
}

int main() {
    static char line[100100];

    int p;
    while (scanf(" %d :", &p), p) {
        Mint::setMod(p);

        fgets(line, sizeof(line), stdin);
        const string s = removeSpace(line);

        try {
            Itr itr = s.cbegin();
            auto ans = expr(itr);
            printf("%s = %d (mod %ld)\n", s.c_str(), int(ans), Mint::mod());
        } catch (const std::runtime_error& e) {
            puts("NG");
        }
    }

    return 0;
}