This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include "test/template.hpp"
using u64 = uint64_t;
#include "src/modint/BarrettReduction.hpp"
mt19937 rnd(random_device{}());
int main() {
rep(i, 0, 1e5) {
const u64 mod = rnd(), a = rnd(), b = rnd(), ans1 = Barrett(mod).mul(a, b), ans2 = a * b % mod;
if(mod == 0) continue;
assert(ans1 == ans2);
}
puts("Hello World");
}
#line 1 "test/modint/BarrettReduction.test.cpp"
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#line 1 "test/template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll INF = LLONG_MAX / 4;
#define rep(i, a, b) for(ll i = a; i < (b); i++)
#define all(a) begin(a), end(a)
#define sz(a) ssize(a)
bool chmin(auto& a, auto b) { return a > b ? a = b, 1 : 0; }
bool chmax(auto& a, auto b) { return a < b ? a = b, 1 : 0; }
#line 3 "test/modint/BarrettReduction.test.cpp"
using u64 = uint64_t;
#line 1 "src/modint/BarrettReduction.hpp"
// using u64 = uint64_t;
struct Barrett { // mod < 2^32
u64 m, im;
Barrett(u64 mod) : m(mod), im(-1ULL / m + 1) {}
// input: a * b < 2^64, output: a * b % mod
u64 mul(u64 a, u64 b) const {
a *= b;
u64 x = ((__uint128_t)a * im) >> 64;
a -= x * m;
if((ll)a < 0) a += m;
return a;
}
};
#line 5 "test/modint/BarrettReduction.test.cpp"
mt19937 rnd(random_device{}());
int main() {
rep(i, 0, 1e5) {
const u64 mod = rnd(), a = rnd(), b = rnd(), ans1 = Barrett(mod).mul(a, b), ans2 = a * b % mod;
if(mod == 0) continue;
assert(ans1 == ans2);
}
puts("Hello World");
}