UOJ Logo WrongAnswer的博客

博客

模意义下的有理数运算模板,求hack

2016-10-12 16:03:16 By WrongAnswer

由于要在学校出校内训练,以后要出些卡操作次数的交互题什么的,于是最近就开始做准备

首先是仿照NOI2016国王饮水记写了个有理数类 Rational,可以支持模意义下的有理数运算 +-*/,比较运算 ==!=

可以指定模数

由于是模意义下的,不能比较两个数的大小

这样就可以出一些卡运算次数和精度的题了(比如计算概率和期望之类的题,或者某些数据结构题)

然而不知道有没写错,如果有错的话求hack

class Rational{
    public:
        Rational();
        Rational(int x);
        Rational(long long x);

        friend Rational operator + (const Rational &a, const Rational &b);
        friend Rational operator + (const Rational &a, int x);
        friend Rational operator + (int x, const Rational &a);
        friend Rational operator + (const Rational &a, long long x);
        friend Rational operator + (long long x, const Rational &a);

        friend Rational operator - (const Rational &a, const Rational &b);
        friend Rational operator - (const Rational &a, int x);
        friend Rational operator - (int x, const Rational &a);
        friend Rational operator - (const Rational &a, long long x);
        friend Rational operator - (long long x, const Rational &a);

        friend Rational operator * (const Rational &a, const Rational &b);
        friend Rational operator * (const Rational &a, int x);
        friend Rational operator * (int x, const Rational &a);
        friend Rational operator * (const Rational &a, long long x);
        friend Rational operator * (long long x, const Rational &a);

        friend Rational operator / (const Rational &a, const Rational &b);
        friend Rational operator / (const Rational &a, int x);
        friend Rational operator / (int x, const Rational &a);
        friend Rational operator / (const Rational &a, long long x);
        friend Rational operator / (long long x, const Rational &a);

        friend bool operator == (const Rational &a, const Rational &b);
        friend bool operator != (const Rational &a, const Rational &b);

        Rational & operator += (int x);
        Rational & operator += (long long x);
        Rational & operator += (const Rational &b);

        Rational & operator -= (int x);
        Rational & operator -= (long long x);
        Rational & operator -= (const Rational &b);

        Rational & operator *= (int x);
        Rational & operator *= (long long x);
        Rational & operator *= (const Rational &b);

        Rational & operator /= (int x);
        Rational & operator /= (long long x);
        Rational & operator /= (const Rational &b);

        friend Rational operator - (const Rational &a);

    private:
        static const int M = 1000000007;

        int a, b;
};

Rational::Rational() {
    a = 0;
    b = 1;
}

Rational::Rational(int x) {
    x %= M;
    if (x < 0) x += M;
    a = x;
    b = 1;
}

Rational::Rational(long long x) {
    x %= M;
    if (x < 0) x += M;
    a = x;
    b = 1;
}

Rational operator + (const Rational &a, const Rational &b) {
    Rational ret;
    ret.a = (a.a * (long long)b.b + a.b * (long long)b.a) % Rational::M;
    ret.b = a.b * (long long)b.b % Rational::M;
    return ret;
}

Rational operator + (const Rational &a, int x) {
    return a + Rational(x);
}

Rational operator + (int x, const Rational &a) {
    return Rational(x) + a;
}

Rational operator + (const Rational &a, long long x) {
    return a + Rational(x);
}

Rational operator + (long long x, const Rational &a) {
    return Rational(x) + a;
}

Rational operator - (const Rational &a, const Rational &b) {
    return a + (-b);
}

Rational operator - (const Rational &a, int x) {
    return a - Rational(x);
}

Rational operator - (int x, const Rational &a) {
    return Rational(x) - a;
}

Rational operator - (const Rational &a, long long x) {
    return a - Rational(x);
}

Rational operator - (long long x, const Rational &a) {
    return Rational(x) - a;
}

Rational operator * (const Rational &a, const Rational &b) {
    Rational ret;
    ret.a = a.a * (long long)b.a % Rational::M;
    ret.b = a.b * (long long)b.b % Rational::M;
    return ret;
}

Rational operator * (const Rational &a, int x) {
    return a * Rational(x);
}

Rational operator * (int x, const Rational &a) {
    return Rational(x) * a;
}

Rational operator * (const Rational &a, long long x) {
    return a * Rational(x);
}

Rational operator * (long long x, const Rational &a) {
    return Rational(x) * a;
}

Rational operator / (const Rational &a, const Rational &b) {
    Rational ret;
    ret.a = a.a * (long long)b.b % Rational::M;
    ret.b = a.b * (long long)b.a % Rational::M;
    return ret;
}

Rational operator / (const Rational &a, int x) {
    return a / Rational(x);
}

Rational operator / (int x, const Rational &a) {
    return Rational(x) / a;
}

Rational operator / (const Rational &a, long long x) {
    return a / Rational(x);
}

Rational operator / (long long x, const Rational &a) {
    return Rational(x) / a;
}

bool operator == (const Rational &a, const Rational &b) {
    return a.a * (long long)b.b % Rational::M == a.b * (long long)b.a % Rational::M;
}

bool operator != (const Rational &a, const Rational &b) {
    return !(a == b);
}

Rational & Rational::operator += (int x) {
    *this = *this + Rational(x);
    return *this;
}

Rational & Rational::operator += (long long x) {
    *this = *this + Rational(x);
    return *this;
}

Rational & Rational::operator += (const Rational &b) {
    *this = *this + b;
    return *this;
}

Rational & Rational::operator -= (int x) {
    *this = *this - Rational(x);
    return *this;
}

Rational & Rational::operator -= (long long x) {
    *this = *this - Rational(x);
    return *this;
}

Rational & Rational::operator -= (const Rational &b) {
    *this = *this - b;
    return *this;
}

Rational & Rational::operator *= (int x) {
    *this = *this * Rational(x);
    return *this;
}

Rational & Rational::operator *= (long long x) {
    *this = *this * Rational(x);
    return *this;
}

Rational & Rational::operator *= (const Rational &b) {
    *this = *this * b;
    return *this;
}

Rational & Rational::operator /= (int x) {
    *this = *this / Rational(x);
    return *this;
}

Rational & Rational::operator /= (long long x) {
    *this = *this / Rational(x);
    return *this;
}

Rational & Rational::operator /= (const Rational &b) {
    *this = *this / b;
    return *this;
}

Rational operator - (const Rational &a) {
    Rational ret = a;
    ret.a = -ret.a;
    if (ret.a < 0) ret.a += Rational::M;
    return ret;
}

评论

Trinkle
%%%
xyx0711
@@@@
ftiasch
一般来说用 += 来实现 + 会好一点,你这样实现的话,两个实现都会有一次拷贝构造,反过来的话,inplace oper 可以做成 inplace 的。
dick32165401
%%%
3A17K
%%%
chentong
%%%
liu_cheng_ao
模意义下怎么处理0/0呢

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。