#1184714 (C++23(gcc16)) No.3687 Coprime Count

• 問題: No.3687 Coprime Count
• ユーザー: 秋ナス🍆
• 提出日時: 2026-09-07 06:49:01
• 言語: C++23(gcc16) (gcc 16.1.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 385 ms / 2,000 ms
• コード長: 25,817 bytes
• コンパイル時間: 6,235 ms
• コンパイル使用メモリ: 396,236 KB
• 実行使用メモリ: 255,376 KB
• 最終ジャッジ日時: 2026-09-07 06:49:12
• 合計ジャッジ時間: 9,423 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
sample	AC * 3
other	AC * 10

ソースコード

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

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <string>
#include <tuple>
#include <type_traits>
#include <utility>
#include <vector>

#if defined(__unix__) || defined(__APPLE__)
#include <unistd.h>
#endif

template <typename T>
std::istream& operator>>(std::istream& is, std::vector<T>& v);

template <typename T1, typename T2>
std::istream& operator>>(std::istream& is, std::pair<T1, T2>& p);

template <typename... Args>
std::istream& operator>>(std::istream& is, std::tuple<Args...>& t);

namespace input_detail {

#ifdef LOCAL

inline std::size_t& read_count() {
    static std::size_t count = 0;
    return count;
}

inline bool& failed_read() {
    static bool failed = false;
    return failed;
}

inline bool stdin_is_terminal() {
#if defined(__unix__) || defined(__APPLE__)
    return isatty(fileno(stdin));
#else
    return false;
#endif
}

struct EndOfInputChecker {
    ~EndOfInputChecker() {
        if (stdin_is_terminal() || failed_read() || std::cin.bad()) return;

        std::cin >> std::ws;
        std::string token;
        if (std::cin >> token) {
            std::cerr << "[input error] 入力が余っています。\n"
                      << "  最初に余った値: " << token << '\n'
                      << "  N と M、H と W、辺数 m、配列長 n などを間違えていないか確認してください。\n";
            std::abort();
        }
    }
};

inline void ensure_end_checker() {
    static EndOfInputChecker checker;
    (void)checker;
}

inline void begin_input() {
    ensure_end_checker();
}

template <typename T>
void read_one(std::istream& is, T& value) {
    if (&is != &std::cin) {
        is >> value;
        return;
    }
    ensure_end_checker();
    ++read_count();
    if (!(is >> value)) {
        failed_read() = true;
        std::cerr << "[input error] 入力が足りないか、型が合いません。\n"
                  << "  " << read_count() << " 個目の値を読み込めませんでした。\n"
                  << "  N と M、H と W、辺数 m、配列長 n などを間違えていないか確認してください。\n";
        std::abort();
    }
}

#else

inline void begin_input() {
}

template <typename T>
void read_one(std::istream& is, T& value) {
    is >> value;
}

#endif

template <typename... Args>
void read_values(Args&... args) {
    (read_one(std::cin, args), ...);
}

}

struct FastIO {
    FastIO() {
        std::ios_base::sync_with_stdio(false);
        std::cin.tie(nullptr);
    }
};
inline FastIO fast_io_init;

template <typename T1, typename T2>
std::istream& operator>>(std::istream& is, std::pair<T1, T2>& p) {
    input_detail::read_one(is, p.first);
    input_detail::read_one(is, p.second);
    return is;
}

template <typename Tuple, std::size_t... I>
void read_tuple_impl(std::istream& is, Tuple& t, std::index_sequence<I...>) {
    (..., input_detail::read_one(is, std::get<I>(t)));
}

template <typename... Args>
std::istream& operator>>(std::istream& is, std::tuple<Args...>& t) {
    read_tuple_impl(is, t, std::index_sequence_for<Args...>{});
    return is;
}

template <typename T>
std::istream& operator>>(std::istream& is, std::vector<T>& v) {
    for (auto& elem : v) {
        input_detail::read_one(is, elem);
    }
    return is;
}

template <typename T>
struct is_pair : std::false_type {};
template <typename T1, typename T2>
struct is_pair<std::pair<T1, T2>> : std::true_type {};

template <typename T>
struct is_tuple : std::false_type {};
template <typename... Args>
struct is_tuple<std::tuple<Args...>> : std::true_type {};

template <typename T>
struct is_vector : std::false_type {};
template <typename T>
struct is_vector<std::vector<T>> : std::true_type {};

template <typename T>
void adjust_zero_indexed(T& val) {
    using DecayedT = std::decay_t<T>;
    if constexpr (is_pair<DecayedT>::value) {
        adjust_zero_indexed(val.first);
        adjust_zero_indexed(val.second);
    } else if constexpr (is_tuple<DecayedT>::value) {
        std::apply([](auto&... args) { (adjust_zero_indexed(args), ...); }, val);
    } else if constexpr (is_vector<DecayedT>::value) {
        for (auto& elem : val) {
            adjust_zero_indexed(elem);
        }
    } else if constexpr (std::is_arithmetic_v<DecayedT> && !std::is_same_v<DecayedT, char> && !std::is_same_v<DecayedT, signed char> &&
                         !std::is_same_v<DecayedT, unsigned char> && !std::is_same_v<DecayedT, wchar_t> &&
#if defined(__cpp_char8_t)
                         !std::is_same_v<DecayedT, char8_t> &&
#endif
                         !std::is_same_v<DecayedT, char16_t> && !std::is_same_v<DecayedT, char32_t> && !std::is_same_v<DecayedT, bool>) {
        --val;
    } else {

    }
}

using default_type = long;

template <typename... Args>
void read(Args&... args) {
    input_detail::read_values(args...);
}

template <typename T = default_type>
T read_val() {
    T val;
    input_detail::read_one(std::cin, val);
    return val;
}

template <typename T1 = default_type, typename T2 = default_type>
std::pair<T1, T2> read_pair() {
    std::pair<T1, T2> p;
    input_detail::begin_input();
    std::cin >> p;
    return p;
}

template <typename... Args>
std::tuple<Args...> read_tuple() {
    std::tuple<Args...> t;
    input_detail::begin_input();
    std::cin >> t;
    return t;
}

template <typename T = default_type, typename Size, std::enable_if_t<std::is_integral_v<Size> && !std::is_same_v<Size, bool>, int> = 0>
std::vector<T> read_vec(Size n, bool zero_indexed = false) {
    std::vector<T> v(n);
    input_detail::begin_input();
    std::cin >> v;
    if (zero_indexed) {
        adjust_zero_indexed(v);
    }
    return v;
}

template <typename T = default_type>
std::vector<T> read_vec(bool zero_indexed = false) {
    int n;
    input_detail::read_one(std::cin, n);
    return read_vec<T>(n, zero_indexed);
}

template <typename T1 = default_type, typename T2 = default_type, typename Size,
          std::enable_if_t<std::is_integral_v<Size> && !std::is_same_v<Size, bool>, int> = 0>
std::vector<std::pair<T1, T2>> read_vec_pair(Size n, bool zero_indexed = false) {
    return read_vec<std::pair<T1, T2>>(n, zero_indexed);
}

template <typename T1 = default_type, typename T2 = default_type>
std::vector<std::pair<T1, T2>> read_vec_pair(bool zero_indexed = false) {
    int n;
    input_detail::read_one(std::cin, n);
    return read_vec_pair<T1, T2>(n, zero_indexed);
}

template <typename... Args, typename Size, std::enable_if_t<std::is_integral_v<Size> && !std::is_same_v<Size, bool>, int> = 0>
std::vector<std::tuple<Args...>> read_vec_tuple(Size n, bool zero_indexed = false) {
    return read_vec<std::tuple<Args...>>(n, zero_indexed);
}

template <typename... Args>
std::vector<std::tuple<Args...>> read_vec_tuple(bool zero_indexed = false) {
    int n;
    input_detail::read_one(std::cin, n);
    return read_vec_tuple<Args...>(n, zero_indexed);
}

template <typename T = default_type>
std::vector<std::vector<T>> read_vec_grid(int h, int w, bool zero_indexed = false) {
    std::vector<std::vector<T>> grid(h, std::vector<T>(w));
    input_detail::begin_input();
    std::cin >> grid;
    if (zero_indexed) {
        adjust_zero_indexed(grid);
    }
    return grid;
}

template <typename T = default_type>
std::vector<std::vector<T>> read_vec_grid(bool zero_indexed = false) {
    int h, w;
    input_detail::read_values(h, w);
    return read_vec_grid<T>(h, w, zero_indexed);
}

template <typename T = default_type, typename Size, std::enable_if_t<std::is_integral_v<Size> && !std::is_same_v<Size, bool>, int> = 0>
std::vector<std::vector<T>> read_vec_var(Size n, bool zero_indexed = false) {
    std::vector<std::vector<T>> res(n);
    input_detail::begin_input();
    for (int i = 0; i < static_cast<int>(n); ++i) {
        int m;
        input_detail::read_one(std::cin, m);
        res[i] = read_vec<T>(m, zero_indexed);
    }
    return res;
}

template <typename T = default_type>
std::vector<std::vector<T>> read_vec_var(bool zero_indexed = false) {
    int n;
    input_detail::read_one(std::cin, n);
    return read_vec_var<T>(n, zero_indexed);
}

template <typename T = default_type>
T read_zero_idx() {
    T val;
    input_detail::read_one(std::cin, val);
    adjust_zero_indexed(val);
    return val;
}

inline std::vector<std::vector<int>> read_graph(int n, int m, bool directed = false) {
    std::vector<std::vector<int>> g(n);
    input_detail::begin_input();
    for (int i = 0; i < m; ++i) {
        int u = read_zero_idx<int>();
        int v = read_zero_idx<int>();
        g[u].push_back(v);
        if (!directed) {
            g[v].push_back(u);
        }
    }
    return g;
}

inline std::vector<std::vector<int>> read_graph(bool directed = false) {
    int n, m;
    input_detail::read_values(n, m);
    return read_graph(n, m, directed);
}

#include <istream>
#include <numeric>
#include <print>
#include <vector>

#define ALL(a) (a).begin(), (a).end()
using i128 = __int128;

template <typename T, typename U>
inline bool chmin(T& a, const U& b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}

template <typename T, typename U>
inline bool chmax(T& a, const U& b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

template <std::integral T>
inline T div_ceil(T a, T b) {
    if (a > 0) return a / b + (a % b != 0);
    return a / b;
}

template <std::integral T>
inline T div_floor(T a, T b) {
    if (a < 0) return a / b - (a % b != 0);
    return a / b;
}

template <std::integral T>
inline T mod(T a, T m) {
    a %= m;
    if (a < 0) a += m;
    return a;
}

template <typename T>
inline constexpr T INF = std::numeric_limits<T>::max() / 2;

template <>
inline constexpr float INF<float> = std::numeric_limits<float>::infinity();

template <>
inline constexpr double INF<double> = std::numeric_limits<double>::infinity();

template <>
inline constexpr long double INF<long double> = std::numeric_limits<long double>::infinity();

template <typename T>
auto make_vector(size_t size, T&& initial_value) {
    return std::vector<std::decay_t<T>>(size, std::forward<T>(initial_value));
}

template <typename... Args>
auto make_vector(size_t size, Args&&... args) {
    auto inner = make_vector(std::forward<Args>(args)...);
    return std::vector<decltype(inner)>(size, inner);
}

template <typename T = int>
inline std::vector<T> iota_vec(int n, T start = 0) {
    std::vector<T> v(n);
    std::iota(v.begin(), v.end(), start);
    return v;
}

template <typename T>
inline std::vector<T> doubled_vec(const std::vector<T>& v) {
    std::vector<T> res;
    res.reserve(v.size() * 2);
    res.insert(res.end(), v.begin(), v.end());
    res.insert(res.end(), v.begin(), v.end());
    return res;
}

inline void Yes(bool b = true) {
    std::println("{}", (b ? "Yes" : "No"));
}

inline void No() {
    std::println("No");
}

#ifdef LOCAL
#include <utility/debug.hpp>
#else
#define debug(...)
#endif

#include <algorithm>
#include <array>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstdint>
#include <limits>
#include <numeric>
#include <random>
#include <vector>

namespace internal {

inline long long mod_mul(long long a, long long b, long long mod) {
    return (__int128)a * b % mod;
}

inline long long mod_pow(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = mod_mul(result, base, mod);
        base = mod_mul(base, base, mod);
        exp >>= 1;
    }
    return result;
}

inline long long ceil_div(long long x, long long y) {
    long long q = x / y;
    long long r = x % y;
    if (r > 0) ++q;
    return q;
}

inline long long isqrt_floor(long long x) {
    if (x <= 0) return 0;
    long long r = static_cast<long long>(std::sqrt(static_cast<long double>(x)));
    while ((r + 1) <= x / (r + 1))
        ++r;
    while (r > x / r)
        --r;
    return r;
}

}

inline bool is_prime_mr(long long n) {
    if (n < 2) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0) return false;

    long long d = n - 1;
    int r = 0;
    while (d % 2 == 0) {
        d /= 2;
        r++;
    }

    static constexpr std::array<long long, 7> witnesses = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};

    for (long long a : witnesses) {
        long long a_mod = a % n;
        if (a_mod == 0) continue;
        long long x = internal::mod_pow(a_mod, d, n);
        if (x == 1 || x == n - 1) continue;

        bool composite = true;
        for (int i = 0; i < r - 1; i++) {
            x = (__int128)x * x % n;
            if (x == n - 1) {
                composite = false;
                break;
            }
        }
        if (composite) return false;
    }
    return true;
}

inline std::vector<std::pair<long long, long long>> factorize(long long n) {
    std::vector<std::pair<long long, long long>> result;
    if (n <= 1) return result;
    for (long long p = 2; p <= n / p; p++) {
        if (n % p == 0) {
            long long cnt = 0;
            while (n % p == 0) {
                n /= p;
                cnt++;
            }
            result.emplace_back(p, cnt);
        }
    }
    if (n > 1) result.emplace_back(n, 1);
    return result;
}

namespace internal {

inline long long pollard_rho(long long n) {
    if (n % 2 == 0) return 2;
    if (is_prime_mr(n)) return n;

    static std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());

    while (true) {
        long long c = rng() % (n - 1) + 1;
        auto f = [&](long long x) { return (mod_mul(x, x, n) + c) % n; };

        long long x = rng() % (n - 2) + 2;
        long long y = x;
        long long g = 1;

        while (g == 1) {
            long long ys = y;
            long long q = 1;
            constexpr int batch = 128;

            for (int r = 1; g == 1; r <<= 1) {
                x = y;
                for (int i = 0; i < r; i++)
                    y = f(y);
                for (int k = 0; g == 1 && k < r; k += batch) {
                    ys = y;
                    int bound = std::min(batch, r - k);
                    for (int i = 0; i < bound; i++) {
                        y = f(y);
                        q = mod_mul(q, std::abs(x - y), n);
                    }
                    g = std::gcd(q, n);
                }
            }

            if (g == n) {
                g = 1;
                while (g == 1) {
                    ys = f(ys);
                    g = std::gcd(std::abs(x - ys), n);
                }
            }
        }
        if (g != n) return g;
    }
}

inline void collect_factors(long long n, std::vector<long long>& result) {
    if (n <= 1) return;
    if (is_prime_mr(n)) {
        result.push_back(n);
        return;
    }
    long long d = pollard_rho(n);
    collect_factors(d, result);
    collect_factors(n / d, result);
}

}

inline std::vector<std::pair<long long, long long>> factorize_fast(long long n) {
    std::vector<long long> primes;
    internal::collect_factors(n, primes);
    std::sort(primes.begin(), primes.end());

    std::vector<std::pair<long long, long long>> result;
    for (long long p : primes) {
        if (!result.empty() && result.back().first == p) {
            result.back().second++;
        } else {
            result.emplace_back(p, 1);
        }
    }
    return result;
}

inline std::vector<long long> divisors(long long n) {
    if (n <= 0) return {};

    std::vector<long long> result = {1};
    for (auto [p, e] : factorize_fast(n)) {
        int sz = static_cast<int>(result.size());
        long long pw = 1;
        for (long long i = 0; i < e; i++) {
            pw *= p;
            for (int j = 0; j < sz; j++) {
                result.push_back(result[j] * pw);
            }
        }
    }

    std::sort(result.begin(), result.end());
    return result;
}

inline long long divisor_count(long long n) {
    if (n <= 0) return 0;
    long long ans = 1;
    for (auto [p, e] : factorize_fast(n)) {
        ans *= (e + 1);
    }
    return ans;
}

inline long long divisor_sum(long long n) {
    if (n <= 0) return 0;
    long long ans = 1;
    for (auto [p, e] : factorize_fast(n)) {
        long long term = 1;
        long long cur = 1;
        for (long long i = 0; i < e; i++) {
            cur *= p;
            term += cur;
        }
        ans *= term;
    }
    return ans;
}

inline long long divisor_sum_mod(long long n, long long mod) {
    if (n <= 0 || mod <= 0) return 0;
    long long ans = 1 % mod;
    for (auto [p, e] : factorize_fast(n)) {
        long long term = 1 % mod;
        long long cur = 1 % mod;
        long long p_mod = p % mod;
        for (long long i = 0; i < e; i++) {
            cur = static_cast<long long>((__int128)cur * p_mod % mod);
            term = (term + cur) % mod;
        }
        ans = static_cast<long long>((__int128)ans * term % mod);
    }
    return ans;
}

struct Eratosthenes {
    std::vector<bool> is_prime_table;
    std::vector<long long> prime_list;
    std::vector<int> min_factor;

    explicit Eratosthenes(int n) {
        if (n < 0) n = 0;
        is_prime_table.assign(n + 1, true);
        min_factor.assign(n + 1, 0);
        is_prime_table[0] = false;
        if (n >= 1) {
            is_prime_table[1] = false;
            min_factor[1] = 1;
        }

        for (int i = 2; i <= n; i++) {
            if (is_prime_table[i]) {
                prime_list.push_back(i);
                min_factor[i] = i;
                for (long long j = (long long)i * i; j <= n; j += i) {
                    is_prime_table[j] = false;
                    if (min_factor[j] == 0) min_factor[j] = i;
                }
            }
        }
    }

    bool is_prime(int n) const { return 0 <= n && n < static_cast<int>(is_prime_table.size()) && is_prime_table[n]; }

    const std::vector<long long>& primes() const { return prime_list; }

    std::vector<std::pair<long long, long long>> factorize(int n) const {
        if (n <= 1 || n >= static_cast<int>(min_factor.size())) return {};
        std::vector<std::pair<long long, long long>> result;
        while (n > 1) {
            int p = min_factor[n];
            long long cnt = 0;
            while (min_factor[n] == p) {
                n /= p;
                cnt++;
            }
            result.emplace_back(p, cnt);
        }
        return result;
    }

    std::vector<long long> divisors(int n) const {
        if (n <= 0 || n >= static_cast<int>(min_factor.size())) return {};
        std::vector<long long> result = {1};
        for (auto [p, e] : factorize(n)) {
            int sz = static_cast<int>(result.size());
            long long pw = 1;
            for (long long i = 0; i < e; i++) {
                pw *= p;
                for (int j = 0; j < sz; j++) {
                    result.push_back(result[j] * pw);
                }
            }
        }
        return result;
    }

    long long divisor_count(int n) const {
        if (n <= 0 || n >= static_cast<int>(min_factor.size())) return 0;
        long long ans = 1;
        for (auto [p, e] : factorize(n)) {
            ans *= (e + 1);
        }
        return ans;
    }

    long long divisor_sum(int n) const {
        if (n <= 0 || n >= static_cast<int>(min_factor.size())) return 0;
        long long ans = 1;
        for (auto [p, e] : factorize(n)) {
            long long term = 1;
            long long cur = 1;
            for (long long i = 0; i < e; i++) {
                cur *= p;
                term += cur;
            }
            ans *= term;
        }
        return ans;
    }
};

struct LinearSieve {
    std::vector<long long> primes;
    std::vector<int> min_factor;
    std::vector<int> phi;
    std::vector<int> mobius;

    explicit LinearSieve(int n) {
        if (n < 0) n = 0;
        min_factor.assign(n + 1, 0);
        phi.assign(n + 1, 0);
        mobius.assign(n + 1, 0);
        if (n >= 1) {
            phi[1] = 1;
            mobius[1] = 1;
        }

        for (int i = 2; i <= n; i++) {
            if (min_factor[i] == 0) {

                primes.push_back(i);
                min_factor[i] = i;
                phi[i] = i - 1;
                mobius[i] = -1;
            }

            for (long long p : primes) {
                if (p * i > n) break;
                int pi = static_cast<int>(p * i);
                min_factor[pi] = static_cast<int>(p);

                if (i % p == 0) {

                    phi[pi] = phi[i] * static_cast<int>(p);
                    mobius[pi] = 0;
                    break;
                } else {

                    phi[pi] = phi[i] * (static_cast<int>(p) - 1);
                    mobius[pi] = -mobius[i];
                }
            }
        }
    }

    bool is_prime(int n) const { return n >= 2 && n < static_cast<int>(min_factor.size()) && min_factor[n] == n; }

    std::vector<std::pair<long long, long long>> factorize(int n) const {
        if (n <= 1 || n >= static_cast<int>(min_factor.size())) return {};
        std::vector<std::pair<long long, long long>> result;
        while (n > 1) {
            int p = min_factor[n];
            long long cnt = 0;
            while (n % p == 0) {
                n /= p;
                cnt++;
            }
            result.emplace_back(p, cnt);
        }
        return result;
    }
};

inline std::vector<long long> segment_sieve(long long L, long long R) {
    if (L < 2) L = 2;
    if (R < L) return {};

    long long sqrtR = internal::isqrt_floor(R);
    assert(sqrtR <= std::numeric_limits<int>::max() && "segment_sieve: sqrt(R) must fit in int for Eratosthenes.");
    if (sqrtR > std::numeric_limits<int>::max()) return {};
    Eratosthenes sieve(static_cast<int>(sqrtR));
    const auto& small_primes = sieve.primes();

    std::vector<bool> is_prime(R - L + 1, true);

    for (long long p : small_primes) {
        long long start = std::max(1LL * p * p, internal::ceil_div(L, p) * 1LL * p);

        for (long long j = start; j <= R; j += p) {
            is_prime[j - L] = false;
        }
    }

    std::vector<long long> result;
    for (long long i = L; i <= R; i++) {
        if (is_prime[i - L]) result.push_back(i);
    }
    return result;
}

inline std::vector<bool> segment_sieve_bool(long long L, long long R) {
    if (R < L) return {};

    std::vector<bool> result(R - L + 1, true);
    if (L < 2) {
        long long last = std::min(R, 1LL);
        if (last >= L) {
            std::fill(result.begin(), result.begin() + (last - L + 1), false);
        }
    }

    if (R < 2) return result;
    long long sqrtR = internal::isqrt_floor(R);
    assert(sqrtR <= std::numeric_limits<int>::max() && "segment_sieve_bool: sqrt(R) must fit in int for Eratosthenes.");
    if (sqrtR > std::numeric_limits<int>::max()) return {};
    Eratosthenes sieve(static_cast<int>(sqrtR));
    const auto& small_primes = sieve.primes();

    for (long long p : small_primes) {
        long long start = std::max(1LL * p * p, internal::ceil_div(L, p) * 1LL * p);

        for (long long j = start; j <= R; j += p) {
            result[j - L] = false;
        }
    }

    return result;
}

inline long long count_primes_range(long long L, long long R) {
    auto primes = segment_sieve(L, R);
    return primes.size();
}

inline std::vector<long long> distinct_prime_factor_count_table(int n) {
    if (n < 0) return {};
    std::vector<long long> count(n + 1, 0);
    for (int i = 2; i <= n; i++) {
        if (count[i] == 0) {
            for (int j = i; j <= n; j += i) {
                count[j]++;
            }
        }
    }
    return count;
}

inline std::vector<long long> total_prime_factor_count_table(int n) {
    if (n < 0) return {};
    std::vector<long long> count(n + 1, 0);
    std::vector<int> min_factor(n + 1, 0);
    for (int i = 2; i <= n; i++) {
        if (min_factor[i] == 0) {
            for (int j = i; j <= n; j += i) {
                if (min_factor[j] == 0) min_factor[j] = i;
            }
        }
        count[i] = count[i / min_factor[i]] + 1;
    }
    return count;
}

inline std::vector<long long> prime_count_table(int n) {
    if (n < 0) return {};
    std::vector<bool> is_prime(n + 1, true);
    std::vector<long long> cnt(n + 1, 0);
    if (n >= 0) is_prime[0] = false;
    if (n >= 1) is_prime[1] = false;

    for (int i = 2; i <= n; i++) {
        if (is_prime[i]) {
            for (int j = i * 2; j <= n; j += i)
                is_prime[j] = false;
        }
        cnt[i] = cnt[i - 1] + is_prime[i];
    }
    return cnt;
}

inline long long euler_phi(long long n) {
    if (n <= 0) return 0;
    long long result = n;
    for (long long p = 2; p <= n / p; p++) {
        if (n % p == 0) {
            while (n % p == 0)
                n /= p;
            result -= result / p;
        }
    }
    if (n > 1) result -= result / n;
    return result;
}

inline std::vector<long long> divisor_count_table(int n) {
    if (n < 0) return {};
    std::vector<long long> count(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j += i) {
            count[j]++;
        }
    }
    return count;
}

inline std::vector<long long> divisor_sum_table(int n) {
    if (n < 0) return {};
    std::vector<long long> sum(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j += i) {
            sum[j] += i;
        }
    }
    return sum;
}

void solve() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long N, M;
    read(N, M);
    LinearSieve sieve(N + N);
    long ans = 0;
    for (int i = 1; i <= N; i++) {
        ans += (sieve.mobius[i] * (N / i) * (M / i));
    }
    println("{}", ans);
}

int main() {
    solve();
}