verify/unit_test/sqrt_floor.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 "../../math/sqrt_floor.hpp"
#include "../../math/random_number_generator.hpp"

RandomNumberGenerator rnd;

void test() {
    assert(sqrt_floor(0) == 0);
    assert(sqrt_floor(1) == 1);
    assert(sqrt_floor(4) == 2);
    assert(sqrt_floor(9) == 3);
    assert(sqrt_floor(16) == 4);

    assert(sqrt_floor(2) == 1);
    assert(sqrt_floor(3) == 1);
    assert(sqrt_floor(5) == 2);
    assert(sqrt_floor(8) == 2);
    assert(sqrt_floor(10) == 3);

    assert(sqrt_floor(1000000000000000000LL) == 1000000000);
    assert(sqrt_floor(999999999999999999LL) == 999999999);

    assert(sqrt_floor(9223372030926249001LL) == 3037000499LL);
    assert(sqrt_floor(9223372036854775807LL) == 3037000499LL);

    for(int i = 0; i < 1e7; i++) {
        long long a = rnd(INT64_MAX);
        unsigned long long root = sqrt_floor(a);
        assert(root * root <= a);
        assert((root + 1) * (root + 1) > a);
    }

    for(int i = 0; i < 1e7; i++) {
        long long a = rnd(INT32_MAX);
        long long a2 = a * a;
        assert(sqrt_floor(a2) == a);
    }

    cerr << "All tests passed" << endl;
}

int main() {
    test();
    int A, B;
    cin >> A >> B;
    cout << A + B << endl;

    return 0;
}

#line 1 "verify/unit_test/sqrt_floor.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/aplusb"

#include <bits/stdc++.h>
using namespace std;

#line 1 "math/sqrt_floor.hpp"
long long sqrt_floor(long long N) {
    assert(0 <= N);
    unsigned long long root = sqrtl(N);
    while(root * root > N) root--;
    while((root + 1) * (root + 1) <= N) root++;
    return root;
}
#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/sqrt_floor.test.cpp"

RandomNumberGenerator rnd;

void test() {
    assert(sqrt_floor(0) == 0);
    assert(sqrt_floor(1) == 1);
    assert(sqrt_floor(4) == 2);
    assert(sqrt_floor(9) == 3);
    assert(sqrt_floor(16) == 4);

    assert(sqrt_floor(2) == 1);
    assert(sqrt_floor(3) == 1);
    assert(sqrt_floor(5) == 2);
    assert(sqrt_floor(8) == 2);
    assert(sqrt_floor(10) == 3);

    assert(sqrt_floor(1000000000000000000LL) == 1000000000);
    assert(sqrt_floor(999999999999999999LL) == 999999999);

    assert(sqrt_floor(9223372030926249001LL) == 3037000499LL);
    assert(sqrt_floor(9223372036854775807LL) == 3037000499LL);

    for(int i = 0; i < 1e7; i++) {
        long long a = rnd(INT64_MAX);
        unsigned long long root = sqrt_floor(a);
        assert(root * root <= a);
        assert((root + 1) * (root + 1) > a);
    }

    for(int i = 0; i < 1e7; i++) {
        long long a = rnd(INT32_MAX);
        long long a2 = a * a;
        assert(sqrt_floor(a2) == a);
    }

    cerr << "All tests passed" << endl;
}

int main() {
    test();
    int A, B;
    cin >> A >> B;
    cout << A + B << endl;

    return 0;
}