library
This documentation is automatically generated by online-judge-tools/verification-helper
test/unit/modint2305843009213693951.test.cpp
- View this file on GitHub
- Last update: 2026-10-23 22:42:06+09:00
- Problem: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A
Depends on
Code
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <cassert>
#include <cstdint>
#include <iostream>
#include <limits>
#include <random>
#include "math/modint2305843009213693951.hpp"
using mint = modint2305843009213693951;
using i128 = __int128;
constexpr uint64_t P = (uint64_t(1) << 61) - 1;
uint64_t norm(i128 x) {
x %= i128(P);
if (x < 0) x += P;
return uint64_t(x);
}
int main() {
static_assert(mint::mod() == P);
std::mt19937_64 rng(7959);
auto gen = [&]() -> uint64_t {
switch (rng() % 6) {
case 0: return 0;
case 1: return P - 1;
case 2: return 1;
case 3: return rng() % 1000;
default: return rng() % P;
}
};
for (int t = 0; t < 100000; t++) {
uint64_t a = gen(), b = gen();
mint x = a, y = b;
assert(x.val() == a && y.val() == b);
assert((x + y).val() == norm(i128(a) + b));
assert((x - y).val() == norm(i128(a) - b));
assert((x * y).val() == norm(i128(a) * b));
assert((-x).val() == norm(-i128(a)));
if (b != 0) {
mint q = x / y;
assert(q * y == x);
assert((y.inv() * y).val() == 1);
}
assert((x == y) == (a == b));
assert((x != y) == (a != b));
}
for (int t = 0; t < 2000; t++) {
uint64_t a = gen();
long long n = rng() % 50;
mint x = a, p = 1;
for (int i = 0; i < n; i++) p *= x;
assert(x.pow(n) == p);
}
assert(mint(P).val() == 0);
assert(mint(P) == mint(0));
assert(mint(P + 1).val() == 1);
assert(mint(std::numeric_limits<uint64_t>::max()).val() == norm(i128(std::numeric_limits<uint64_t>::max())));
assert(mint(-1).val() == P - 1);
assert(mint(-1LL).val() == P - 1);
assert(mint(std::numeric_limits<long long>::min()).val() == norm(i128(std::numeric_limits<long long>::min())));
assert(mint(std::numeric_limits<long long>::max()).val() == norm(i128(std::numeric_limits<long long>::max())));
assert(mint(int(-5)).val() == P - 5);
assert(mint::raw(3).val() == 3);
{
mint x = P - 1;
x++;
assert(x.val() == 0);
x--;
assert(x.val() == P - 1);
assert((++x).val() == 0);
assert((--x).val() == P - 1);
}
{
uint64_t a = P - 1;
mint x = a;
assert((x * x).val() == norm(i128(a) * a));
mint y = uint64_t(1) << 60;
assert((y * y).val() == norm(i128(uint64_t(1) << 60) * (uint64_t(1) << 60)));
}
std::cout << "Hello World" << std::endl;
return 0;
}#line 1 "test/unit/modint2305843009213693951.test.cpp"
#define PROBLEM "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A"
#include <cassert>
#include <cstdint>
#include <iostream>
#include <limits>
#include <random>
#line 3 "math/modint2305843009213693951.hpp"
#include <concepts>
#line 5 "math/modint2305843009213693951.hpp"
struct modint2305843009213693951 {
using mint = modint2305843009213693951;
static constexpr uint64_t mod() {
return m;
}
static mint raw(uint64_t v) {
mint x;
x._v = v;
return x;
}
modint2305843009213693951() : _v(0) {}
template <std::unsigned_integral T>
modint2305843009213693951(T v) : _v(reduce(v)) {}
template <std::signed_integral T>
modint2305843009213693951(T v) {
if (v >= 0) {
_v = reduce(uint64_t(v));
} else {
uint64_t x = reduce(uint64_t(0) - uint64_t(v));
_v = x == 0 ? 0 : m - x;
}
}
uint64_t val() const {
return _v;
}
mint& operator++() {
if (++_v == m) _v = 0;
return *this;
}
mint& operator--() {
if (_v == 0) _v = m;
_v--;
return *this;
}
mint operator++(int) {
mint r = *this;
++*this;
return r;
}
mint operator--(int) {
mint r = *this;
--*this;
return r;
}
mint& operator+=(const mint& rhs) {
_v += rhs._v;
if (_v >= m) _v -= m;
return *this;
}
mint& operator-=(const mint& rhs) {
_v += m - rhs._v;
if (_v >= m) _v -= m;
return *this;
}
mint& operator*=(const mint& rhs) {
constexpr uint64_t mask31 = (uint64_t(1) << 31) - 1;
constexpr uint64_t mask30 = (uint64_t(1) << 30) - 1;
uint64_t au = _v >> 31, ad = _v & mask31;
uint64_t bu = rhs._v >> 31, bd = rhs._v & mask31;
uint64_t mid = ad * bu + au * bd;
uint64_t mu = mid >> 30, md = mid & mask30;
_v = reduce((au * bu << 1) + mu + (md << 31) + ad * bd);
return *this;
}
mint& operator/=(const mint& rhs) {
return *this *= rhs.inv();
}
mint operator+() const {
return *this;
}
mint operator-() const {
return mint() - *this;
}
mint pow(long long n) const {
assert(0 <= n);
mint x = *this, r = 1;
while (n) {
if (n & 1) r *= x;
x *= x;
n >>= 1;
}
return r;
}
mint inv() const {
assert(_v != 0);
return pow(m - 2);
}
friend mint operator+(const mint& lhs, const mint& rhs) {
return mint(lhs) += rhs;
}
friend mint operator-(const mint& lhs, const mint& rhs) {
return mint(lhs) -= rhs;
}
friend mint operator*(const mint& lhs, const mint& rhs) {
return mint(lhs) *= rhs;
}
friend mint operator/(const mint& lhs, const mint& rhs) {
return mint(lhs) /= rhs;
}
friend bool operator==(const mint& lhs, const mint& rhs) {
return lhs._v == rhs._v;
}
friend bool operator!=(const mint& lhs, const mint& rhs) {
return lhs._v != rhs._v;
}
private:
static constexpr uint64_t m = (uint64_t(1) << 61) - 1;
static constexpr uint64_t reduce(uint64_t v) {
uint64_t x = (v >> 61) + (v & m);
if (x >= m) x -= m;
return x;
}
uint64_t _v;
};
#line 9 "test/unit/modint2305843009213693951.test.cpp"
using mint = modint2305843009213693951;
using i128 = __int128;
constexpr uint64_t P = (uint64_t(1) << 61) - 1;
uint64_t norm(i128 x) {
x %= i128(P);
if (x < 0) x += P;
return uint64_t(x);
}
int main() {
static_assert(mint::mod() == P);
std::mt19937_64 rng(7959);
auto gen = [&]() -> uint64_t {
switch (rng() % 6) {
case 0: return 0;
case 1: return P - 1;
case 2: return 1;
case 3: return rng() % 1000;
default: return rng() % P;
}
};
for (int t = 0; t < 100000; t++) {
uint64_t a = gen(), b = gen();
mint x = a, y = b;
assert(x.val() == a && y.val() == b);
assert((x + y).val() == norm(i128(a) + b));
assert((x - y).val() == norm(i128(a) - b));
assert((x * y).val() == norm(i128(a) * b));
assert((-x).val() == norm(-i128(a)));
if (b != 0) {
mint q = x / y;
assert(q * y == x);
assert((y.inv() * y).val() == 1);
}
assert((x == y) == (a == b));
assert((x != y) == (a != b));
}
for (int t = 0; t < 2000; t++) {
uint64_t a = gen();
long long n = rng() % 50;
mint x = a, p = 1;
for (int i = 0; i < n; i++) p *= x;
assert(x.pow(n) == p);
}
assert(mint(P).val() == 0);
assert(mint(P) == mint(0));
assert(mint(P + 1).val() == 1);
assert(mint(std::numeric_limits<uint64_t>::max()).val() == norm(i128(std::numeric_limits<uint64_t>::max())));
assert(mint(-1).val() == P - 1);
assert(mint(-1LL).val() == P - 1);
assert(mint(std::numeric_limits<long long>::min()).val() == norm(i128(std::numeric_limits<long long>::min())));
assert(mint(std::numeric_limits<long long>::max()).val() == norm(i128(std::numeric_limits<long long>::max())));
assert(mint(int(-5)).val() == P - 5);
assert(mint::raw(3).val() == 3);
{
mint x = P - 1;
x++;
assert(x.val() == 0);
x--;
assert(x.val() == P - 1);
assert((++x).val() == 0);
assert((--x).val() == P - 1);
}
{
uint64_t a = P - 1;
mint x = a;
assert((x * x).val() == norm(i128(a) * a));
mint y = uint64_t(1) << 60;
assert((y * y).val() == norm(i128(uint64_t(1) << 60) * (uint64_t(1) << 60)));
}
std::cout << "Hello World" << std::endl;
return 0;
}