1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 1 year has passed since last update.

modint

Last updated at Posted at 2022-03-20

自作クラスのインスタンス同士では単純に足し算をすることはできない

仮引数に入っているのは+記号の右辺

左辺値は自分自身、つまり「this」を表す

// modint: mod 計算を int を扱うように扱える構造体
template<int MOD> struct Fp {
    long long val; //this -> value
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) { // 定義
        if (val < 0) val += MOD; // 負なら
    }
    constexpr int getmod() { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0; // 0 以外ならマイナスを付ける
    }
    //modで割ってから計算
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val; //左辺 : val  右辺 : r.val
        if (val >= MOD) val -= MOD;
        return *this; //左辺
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    //ax+by=1を解く
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) { 
            long long t = a / b; // (最大公約数)
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val; //値の比較
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {
        return os << x.val; //左シフト
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t; // a^nの高速化
    }
};


const int MOD = 1000000007;
using mint = Fp<MOD>;

int main() {
    mint a = 423343;
    mint b = 74324;
    mint c = 13231;
    mint d = 8432455;

    cout << (a * b + c) / d << endl;
}
1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?