cp_library
This documentation is automatically generated by online-judge-tools/verification-helper
verify/unit_test/montgomery_modint_32.test.cpp
- View this file on GitHub
- Last update: 2025-03-08 01:15:39+09:00
- Problem: https://judge.yosupo.jp/problem/aplusb
Depends on
Code
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#include <bits/stdc++.h>
using namespace std;
#include "../../data_structure/montgomery_modint_32.hpp"
#include "../../math/random_number_generator.hpp"
using mint = MontgomeryModint32;
RandomNumberGenerator rnd;
void set_test() {
for(int i = 0; i < 1e6; i++) {
int mod = rnd(1e9);
if(mod % 2 == 0) mod += 1;
mint::set_mod(mod);
int v = rnd(mod + 1, 1e9);
assert(mint(v) == v % mod);
}
}
void operator_test(int mod) {
mint::set_mod(mod);
for(int i = 0; i < 1e5; i++) {
int a = rnd(mod);
if(rnd(1e9) % 10 == 0) a = 0;
if(rnd(1e9) % 10 == 0) a = mod - 1;
mint A = a;
assert(A.val() == a);
int b = rnd(mod);
if(rnd(1e9) % 10 == 0) b = 0;
if(rnd(1e9) % 10 == 0) b = mod - 1;
mint B = b;
assert(B.val() == b);
int c = (a + b) % mod;
mint C = A + B;
assert(C.val() == c);
int d = (a + mod - b) % mod;
mint D = A - B;
assert(D.val() == d);
int e = (1LL * a * b) % mod;
mint E = A * B;
assert(E.val() == e);
mint F = rnd(1, mod);
mint G = F.inv();
if(F * G != 1) cerr << mod << endl;
assert(F * G == 1);
}
}
void test() {
set_test();
operator_test(998244353);
operator_test(1000000007);
operator_test(1);
operator_test(3);
operator_test(5);
operator_test(7);
operator_test(11);
operator_test(101);
cerr << "ok" << endl;
}
int main() {
test();
int a, b;
cin >> a >> b;
cout << a + b << endl;
}#line 1 "verify/unit_test/montgomery_modint_32.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"
#include <bits/stdc++.h>
using namespace std;
#line 1 "data_structure/montgomery_modint_32.hpp"
// mod奇数の剰余計算高速
struct MontgomeryModint32 {
using mint = MontgomeryModint32;
using u32 = uint32_t;
using u64 = uint64_t;
u32 _v;
// static変数
// R = 2 ^ 32
static inline u32 MOD;
static inline u32 INV_MOD; // INV_MOD * MOD ≡ 1 (mod 2 ^ 32)
static inline u32 T64; // 2 ^ 64 (mod MOD)
// static関数
static void set_mod(u32 mod) {
MOD = mod;
T64 = -u64(mod) % mod;
INV_MOD = get_inv_mod();
}
// ニュートン法で逆元を求める
static u32 get_inv_mod() {
u32 res = MOD;
for(int i = 0; i < 4; ++i) res *= 2 - MOD * res;
return res;
}
// モンゴメリリダクション
static u32 MR(const u64& v) {
return (v + u64(u32(v) * u32(-INV_MOD)) * MOD) >> 32;
}
mint inv() const { return pow(MOD - 2); }
mint pow(u64 n) const {
mint res(1), mul(*this);
while(n) {
if(n & 1) res *= mul;
mul *= mul;
n >>= 1;
}
return res;
}
u32 val() const {
u32 res = MR(_v);
return res >= MOD ? res - MOD : res;
}
MontgomeryModint32(): _v(0) {}
MontgomeryModint32(long long v): _v(MR((u64(v) + MOD) * T64)) {}
mint operator + () const { return *this; }
mint operator - () const { return mint() - mint(*this); }
mint& operator ++ () { return *this += 1; }
mint& operator -- () { return *this -= 1; }
mint operator ++ (int) { mint res = *this; ++*this; return res; }
mint operator -- (int) { mint res = *this; --*this; return res; }
mint operator + (const mint& r) const { return mint(*this) += r; }
mint operator - (const mint& r) const { return mint(*this) -= r; }
mint operator * (const mint& r) const { return mint(*this) *= r; }
mint operator / (const mint& r) const { return mint(*this) /= r; }
mint& operator += (const mint& r) {
if((_v += r._v) >= 2 * MOD) _v -= 2 * MOD;
return *this;
}
mint& operator -= (const mint& r) {
if((_v += 2 * MOD - r._v) >= 2 * MOD) _v -= 2 * MOD;
return *this;
}
mint& operator *= (const mint& r) {
_v = MR(u64(_v) * r._v);
return *this;
}
mint& operator /= (const mint& r) {
*this *= r.inv();
return *this;
}
bool operator == (const mint& r) const {
return (_v >= MOD ? _v - MOD : _v) == (r._v >= MOD ? r._v - MOD : r._v);
}
bool operator != (const mint& r) const {
return (_v >= MOD ? _v - MOD : _v) != (r._v >= MOD ? r._v - MOD : r._v);
}
friend istream& operator >> (istream& is, mint& x) {
long long t;
is >> t;
x = mint(t);
return is;
}
friend ostream& operator << (ostream& os, const mint& x) {
return os << x.val();
}
};
#line 1 "math/random_number_generator.hpp"
struct RandomNumberGenerator {
mt19937 mt;
RandomNumberGenerator() : mt(random_device()()) {}
long long operator()(long long a, long long b) { return uniform_int_distribution<long long>(a, b - 1)(mt); }
long long operator()(long long b) { return (*this)(0, b); }
};
#line 8 "verify/unit_test/montgomery_modint_32.test.cpp"
using mint = MontgomeryModint32;
RandomNumberGenerator rnd;
void set_test() {
for(int i = 0; i < 1e6; i++) {
int mod = rnd(1e9);
if(mod % 2 == 0) mod += 1;
mint::set_mod(mod);
int v = rnd(mod + 1, 1e9);
assert(mint(v) == v % mod);
}
}
void operator_test(int mod) {
mint::set_mod(mod);
for(int i = 0; i < 1e5; i++) {
int a = rnd(mod);
if(rnd(1e9) % 10 == 0) a = 0;
if(rnd(1e9) % 10 == 0) a = mod - 1;
mint A = a;
assert(A.val() == a);
int b = rnd(mod);
if(rnd(1e9) % 10 == 0) b = 0;
if(rnd(1e9) % 10 == 0) b = mod - 1;
mint B = b;
assert(B.val() == b);
int c = (a + b) % mod;
mint C = A + B;
assert(C.val() == c);
int d = (a + mod - b) % mod;
mint D = A - B;
assert(D.val() == d);
int e = (1LL * a * b) % mod;
mint E = A * B;
assert(E.val() == e);
mint F = rnd(1, mod);
mint G = F.inv();
if(F * G != 1) cerr << mod << endl;
assert(F * G == 1);
}
}
void test() {
set_test();
operator_test(998244353);
operator_test(1000000007);
operator_test(1);
operator_test(3);
operator_test(5);
operator_test(7);
operator_test(11);
operator_test(101);
cerr << "ok" << endl;
}
int main() {
test();
int a, b;
cin >> a >> b;
cout << a + b << endl;
}