test/src/number/min_of_mod_of_linear/min_of_mod_of_linear.test.cpp

• View this file on GitHub
• Last update: 2023-01-02 12:13:30+09:00
• Problem: https://judge.yosupo.jp/problem/min_of_mod_of_linear

Depends on

• Min Of Mod Of Linear (library/number/min_of_mod_of_linear.hpp)

Code

#define PROBLEM "https://judge.yosupo.jp/problem/min_of_mod_of_linear"

#include <iostream>

#include "library/number/min_of_mod_of_linear.hpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;

    for (int test_case_id = 0; test_case_id < t; ++test_case_id) {
        int n, m, a, b;
        std::cin >> n >> m >> a >> b;
        
        std::cout << suisen::min_of_mod_of_linear(n, m, a, b) << std::endl;
    }
}

#line 1 "test/src/number/min_of_mod_of_linear/min_of_mod_of_linear.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/min_of_mod_of_linear"

#include <iostream>

#line 1 "library/number/min_of_mod_of_linear.hpp"



#include <numeric>
#include <vector>

#include <atcoder/math>

namespace suisen {
    // min{ (ax+b) mod m | 0<=x<n }
    int min_of_mod_of_linear(int n, int m, int a, int b) {
        // let k be an integer s.t. 0<=k<m.
        //     ax+b mod M <= k
        // <=> (ax+b-k)/m <= floor((ax+b)/m)
        // <=> floor((ax+b+(m-1-k))/m) <= floor((ax+b)/m)
        // <=> floor((ax+b+(m-1-k))/m)  = floor((ax+b)/m)    (because 0<=m-1-k<m)

        // if there exists an integer x in [0,n) s.t. floor((ax+b+(m-1-k))/m) = floor((ax+b)/m),
        //   floor_sum(n, m, a, b+(m-1-k)) < floor_sum(n, m, a, b) + n
        // holds.

        // Applying binary search on k, we can get min{ (ax+b) mod m | 0<=x<n } in O((log m)^2) time.

        long long v = atcoder::floor_sum(n, m, a, b) + n;

        int l = -1, r = m - 1;
        while (r - l > 1) {
            int k = (l + r) >> 1;
            if (atcoder::floor_sum(n, m, a, b + (m - 1 - k)) < v) {
                r = k;
            } else {
                l = k;
            }
        }
        return r;
    }
} // namespace suisen



#line 6 "test/src/number/min_of_mod_of_linear/min_of_mod_of_linear.test.cpp"

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int t;
    std::cin >> t;

    for (int test_case_id = 0; test_case_id < t; ++test_case_id) {
        int n, m, a, b;
        std::cin >> n >> m >> a >> b;
        
        std::cout << suisen::min_of_mod_of_linear(n, m, a, b) << std::endl;
    }
}

Back to top page