#905034 (C++17) No.2425 Power Range GCD

提出ソース
結果

問題	No.2425 Power Range GCD
ユーザー	Gandalfr
提出日時	2023-08-18 21:19:39
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	15,265 bytes
コンパイル時間	3,405 ms
コンパイル使用メモリ	236,120 KB
実行使用メモリ	144,984 KB
最終ジャッジ日時	2024-05-06 03:06:27
合計ジャッジ時間	13,140 ms
ジャッジサーバーID （参考情報）	judge1 / judge5
このコードへのチャレンジ
（要ログイン）
テストケース

テストケース表示
入力	結果	実行時間実行使用メモリ
testcase_00	AC	1,466 ms 144,984 KB
testcase_01	WA	-
testcase_02	WA	-
testcase_03	WA	-
testcase_04	WA	-
testcase_05	WA	-
testcase_06	WA	-
testcase_07	WA	-
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	AC	1,520 ms 144,728 KB
testcase_16	AC	1,494 ms 144,856 KB
testcase_17	WA	-
testcase_18	WA	-
testcase_19	AC	1,500 ms 144,732 KB
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
権限があれば一括ダウンロードができます
ソースコード

raw source code
#line 1 "playspace/main.cpp"
#include <bits/stdc++.h>
#line 8 "library/gandalfr/other/io_supporter.hpp"

template <typename T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
    for (int i = 0; i < (int)v.size(); i++)
        os << v[i] << (i + 1 != (int)v.size() ? " " : "");
    return os;
}
template <typename T>
std::ostream &operator<<(std::ostream &os, const std::set<T> &st) {
    for (const T &x : st) {
        std::cout << x << " ";
    }
    return os;
}

template <typename T>
std::ostream &operator<<(std::ostream &os, const std::multiset<T> &st) {
    for (const T &x : st) {
        std::cout << x << " ";
    }
    return os;
}
template <typename T>
std::ostream &operator<<(std::ostream &os, const std::deque<T> &dq) {
    for (const T &x : dq) {
        std::cout << x << " ";
    }
    return os;
}
template <typename T1, typename T2>
std::ostream &operator<<(std::ostream &os, const std::pair<T1, T2> &p) {
    os << p.first << ' ' << p.second;
    return os;
}
template <typename T>
std::ostream &operator<<(std::ostream &os, std::queue<T> &q) {
    int sz = q.size();
    while (--sz) {
        os << q.front() << ' ';
        q.push(q.front());
        q.pop();
    }
    os << q.front();
    q.push(q.front());
    q.pop();
    return os;
}

template <typename T>
std::istream &operator>>(std::istream &is, std::vector<T> &v) {
    for (T &in : v)
        is >> in;
    return is;
}
template <typename T1, typename T2>
std::istream &operator>>(std::istream &is, std::pair<T1, T2> &p) {
    is >> p.first >> p.second;
    return is;
}
#line 4 "library/gandalfr/math/prime_number_utility.hpp"

#line 6 "library/gandalfr/math/prime_number_utility.hpp"

#line 6 "library/gandalfr/math/enumeration_utility.hpp"

#line 5 "library/gandalfr/standard/mod_integer.hpp"

inline long long mod_inverse(long long a, int mod) {
    assert(mod > 0);
    long long b = mod, u = 1, v = 0;
    while (b) {
        long long t = a / b;
        a -= t * b, std::swap(a, b);
        u -= t * v, std::swap(u, v);
    }
    u %= mod;
    if (u < 0)
        u += mod;
    return u;
}

// mod_integer<P> a := Pを法とするときの整数型;
template <int mod> class mod_integer {
  private:
    long long val; // 値は必ず 0 <= val < mod に保たれる
    friend mod_integer operator+(const mod_integer &a) { return a; }
    friend mod_integer operator-(const mod_integer &a) { return -a.val; }
    friend mod_integer operator+(const mod_integer &a, const mod_integer &b) {
        return mod_integer(a.val + b.val);
    }
    friend mod_integer operator-(const mod_integer &a, const mod_integer &b) {
        return mod_integer(a.val - b.val);
    }
    friend mod_integer operator*(const mod_integer &a, const mod_integer &b) {
        return mod_integer(a.val * b.val);
    }
    friend mod_integer operator/(const mod_integer &a, const mod_integer &b) {
        return mod_integer((a.val * mod_inverse(b.val, mod)) % mod);
    }

    friend bool operator==(const mod_integer &a, const mod_integer &b) {
        return a.val == b.val;
    }
    friend bool operator!=(const mod_integer &a, const mod_integer &b) {
        return a.val != b.val;
    }

    // map とかに乗せたいので、便宜的に定義
    friend bool operator<(const mod_integer &a, const mod_integer &b) {
        return a.val < b.val;
    }

  public:
    mod_integer(long long n) : val(n) {
        val %= mod;
        if (val < 0)
            val += mod;
    }
    mod_integer() : val(0) {}
    int value() const { return (int)val; }

    mod_integer &operator=(const mod_integer &a) = default;
    mod_integer &operator+=(const mod_integer &a) {
        val += a.val;
        if (val >= mod)
            val -= mod;
        return *this;
    }
    mod_integer &operator-=(const mod_integer &a) {
        val -= a.val;
        if (val < 0)
            val += mod;
        return *this;
    }
    mod_integer &operator*=(const mod_integer &a) {
        (val *= a.val) %= mod;
        return *this;
    }
    mod_integer &operator/=(const mod_integer &a) {
        (val *= mod_inverse(a.val, mod)) %= mod;
        return *this;
    }

    friend std::istream &operator>>(std::istream &is, mod_integer &a) {
        is >> a.val;
        a.val %= mod;
        if (a.val < 0)
            a.val += mod;
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const mod_integer &a) {
        os << a.val;
        return os;
    }
};

// d_mod_integer<P> a := Pを法とするときの整数型;
template <int id> class dynamic_mod_integer {
  private:
    using d_mod_integer = dynamic_mod_integer<id>;
    static inline int mod = 998244353;
    long long val; // 値は必ず 0 <= val < mod に保たれる
    friend d_mod_integer operator+(const d_mod_integer &a) { return a; }
    friend d_mod_integer operator-(const d_mod_integer &a) { return -a.val; }
    friend d_mod_integer operator+(const d_mod_integer &a,
                                   const d_mod_integer &b) {
        return d_mod_integer(a.val + b.val);
    }
    friend d_mod_integer operator-(const d_mod_integer &a,
                                   const d_mod_integer &b) {
        return d_mod_integer(a.val - b.val);
    }
    friend d_mod_integer operator*(const d_mod_integer &a,
                                   const d_mod_integer &b) {
        return d_mod_integer(a.val * b.val);
    }
    friend d_mod_integer operator/(const d_mod_integer &a,
                                   const d_mod_integer &b) {
        return d_mod_integer((a.val * mod_inverse(b.val, mod)) % mod);
    }

    friend bool operator==(const d_mod_integer &a, const d_mod_integer &b) {
        return a.val == b.val;
    }
    friend bool operator!=(const d_mod_integer &a, const d_mod_integer &b) {
        return a.val != b.val;
    }

    // map とかに乗せたいので、便宜的に定義
    friend bool operator<(const d_mod_integer &a, const d_mod_integer &b) {
        return a.val < b.val;
    }

  public:
    dynamic_mod_integer(long long n) : val(n) {
        val %= mod;
        if (val < 0)
            val += mod;
    }
    dynamic_mod_integer() : val(0) {}
    int value() const { return (int)val; }
    static void set_mod(int _mod) {
        assert(_mod >= 0);
        mod = _mod;
    }

    d_mod_integer &operator=(const d_mod_integer &a) = default;
    d_mod_integer &operator+=(const d_mod_integer &a) {
        val += a.val;
        if (val >= mod)
            val -= mod;
        return *this;
    }
    d_mod_integer &operator-=(const d_mod_integer &a) {
        val -= a.val;
        if (val < 0)
            val += mod;
        return *this;
    }
    d_mod_integer &operator*=(const d_mod_integer &a) {
        (val *= a.val) %= mod;
        return *this;
    }
    d_mod_integer &operator/=(const d_mod_integer &a) {
        (val *= mod_inverse(a.val, mod)) %= mod;
        return *this;
    }

    friend std::istream &operator>>(std::istream &is, d_mod_integer &a) {
        is >> a.val;
        a.val %= mod;
        if (a.val < 0)
            a.val += mod;
        return is;
    }
    friend std::ostream &operator<<(std::ostream &os, const d_mod_integer &a) {
        os << a.val;
        return os;
    }
};

using mint = mod_integer<1000000007>;
using _mint = mod_integer<998244353>;
using dmint = dynamic_mod_integer<-1>;
#line 8 "library/gandalfr/math/enumeration_utility.hpp"

template <class T> T power(T x, long long n) {
    T ret = static_cast<T>(1);
    while (n > 0) {
        if (n & 1)
            ret = ret * x;
        x = x * x;
        n >>= 1;
    }
    return ret;
}

long long power(long long x, long long n) {
    long long ret = 1;
    while (n > 0) {
        if (n & 1)
            ret = ret * x;
        x = x * x;
        n >>= 1;
    }
    return ret;
}

long long power(long long x, long long n, int MOD) {
    long long ret = 1;
    x %= MOD;
    while (n > 0) {
        if (n & 1)
            ret = ret * x % MOD;
        x = x * x % MOD;
        n >>= 1;
    }
    return ret;
}

long long power(long long x, long long n, long long MOD) {
    long long ret = 1;
    x %= MOD;
    while (n > 0) {
        if (n & 1)
            ret = (__int128_t)ret * x % MOD;
        x = (__int128_t)x * x % MOD;
        n >>= 1;
    }
    return ret;
}

template <class T> class factorial {
  private:
    static inline std::vector<T> fact{T(1)};

  public:
    factorial() = delete;
    ~factorial() = delete;
    static T get(int n) {
        while (n >= fact.size())
            fact.push_back(fact.back() * fact.size());
        return fact[n];
    }
};
mint (*fact)(int) = factorial<mint>::get;
_mint (*_fact)(int) = factorial<_mint>::get;

template <class T> T permutation(int n, int k) {
    assert(0 <= k && k <= n);
    return factorial<T>::get(n) / factorial<T>::get(n - k);
}
mint (*perm)(int, int) = permutation<mint>;
_mint (*_perm)(int, int) = permutation<_mint>;

template <class T> static T combnation(int n, int k) {
    assert(0 <= k && k <= n);
    return factorial<T>::get(n) /
           (factorial<T>::get(k) * factorial<T>::get(n - k));
}
mint (*comb)(int, int) = combnation<mint>;
_mint (*_comb)(int, int) = combnation<_mint>;
#line 8 "library/gandalfr/math/prime_number_utility.hpp"

/**
 * @see https://drken1215.hatenablog.com/entry/2023/05/23/233000
 */
bool MillerRabin(long long N, const std::vector<long long> &A) {
    long long s = 0, d = N - 1;
    while (d % 2 == 0) {
        ++s;
        d >>= 1;
    }
    for (auto a : A) {
        if (N <= a)
            return true;
        long long t, x = power(a, d, N);
        if (x != 1) {
            for (t = 0; t < s; ++t) {
                if (x == N - 1)
                    break;
                x = (__int128_t)x * x % N;
            }
            if (t == s)
                return false;
        }
    }
    return true;
}

/**
 * @brief 素数判定や列挙をサポートするクラス
 * @brief 素数篩を固定サイズで構築、それをもとに素数列挙などを行う
 */
class Eratosthenes {
  protected:
    static inline int seive_size = (1 << 24);
    static inline std::vector<bool> sieve;
    static inline std::vector<int> primes{2, 3}, movius, min_factor;

    static void make_table() {
        sieve.assign(seive_size, true);
        sieve[0] = sieve[1] = false;
        movius.assign(seive_size, 1);
        min_factor.assign(seive_size, 1);
        for (int i = 2; i <= seive_size; ++i) {
            if (!sieve[i])
                continue;
            movius[i] = -1;
            min_factor[i] = i;
            primes.push_back(i);
            for (int j = i * 2; j < seive_size; j += i) {
                sieve[j] = false;
                movius[j] = ((j / i) % i == 0 ? 0 : -movius[j]);
                if (min_factor[j] == 1)
                    min_factor[j] = i;
            }
        }
    }

    static std::vector<std::pair<long long, int>> fast_factorize(long long n) {
        std::vector<std::pair<long long, int>> ret;
        while (n > 1) {
            if (ret.empty() || ret.back().first != min_factor[n]) {
                ret.push_back({min_factor[n], 1});
            } else {
                ret.back().second++;
            }
            n /= min_factor[n];
        }
        return ret;
    }

    static std::vector<std::pair<long long, int>> naive_factorize(long long n) {
        std::vector<std::pair<long long, int>> ret;
        for (long long p : primes) {
            if (n == 1 || p * p > n)
                break;
            while (n % p == 0) {
                if (ret.empty() || ret.back().first != p)
                    ret.push_back({p, 1});
                else
                    ret.back().second++;
                n /= p;
            }
        }
        if (n != 1)
            ret.push_back({n, 1});
        return ret;
    }

  public:
    Eratosthenes() = delete;
    ~Eratosthenes() = delete;

    static void set_init_size(int size) {
        assert(sieve.empty());
        seive_size = size;
    }

    /**
     * @brief n が素数かを判定
     * @attention if n < (1 << 24) : O(1)
     * @attention else : O(log(N))
     */
    static bool is_prime(long long n) {
        if (sieve.empty())
            make_table();
        assert(1 <= n);

        if (n > 2 && (n & 1LL) == 0) {
            return false;
        } else if (n < seive_size) {
            return sieve[n];
        } else if (n < 4759123141LL) {
            return MillerRabin(n, {2, 7, 61});
        } else {
            return MillerRabin(
                n, {2, 325, 9375, 28178, 450775, 9780504, 1795265022});
        }
    }

    /**
     * @brief 素因数分解する
     * @return factorize(p1^e1 * p2^e2 * ...) => {{p1, e1}, {p2, e2], ...},
     * @return factorize(1) => {}
     * @attention if n < (1 << 24) : O(log(N))
     * @attention if n < (1 << 24) : O(N^(3/2))
     */
    static std::vector<std::pair<long long, int>> factorize(long long n) {
        if (sieve.empty())
            make_table();
        assert(1 <= n);

        if (n < seive_size) {
            return fast_factorize(n);
        } else {
            return naive_factorize(n);
        }
    }

    static int Movius(int n) {
        if (movius.empty())
            make_table();
        assert(1 <= n);
        return movius.at(n);
    }

    /**
     * @brief オイラーのトーシェント関数
     */
    long long totient(long long n) {
        long long ret = 1;
        for (auto [b, e] : factorize(n))
            ret *= power(b, e - 1) * (b - 1);
        return ret;
    }


    static int kth_prime(int k) { return primes.at(k); }
};
#line 4 "playspace/main.cpp"
using namespace std;
using ll = long long;
const int INF = 1001001001;
const int MAXINT = std::numeric_limits<int>::max();
const int MININT = std::numeric_limits<int>::min();
const ll INFLL = 1001001001001001001;
const ll MAXLL = std::numeric_limits<ll>::max();
const ll MINLL = std::numeric_limits<ll>::min();
const ll MOD  = 1000000007;
const ll _MOD = 998244353;
#define rep(i, j, n) for(ll i = (ll)(j); i < (ll)(n); i++)
#define rrep(i, j, n) for(ll i = (ll)(n-1); i >= (ll)(j); i--)
#define all(a) (a).begin(),(a).end()
#define LF cout << endl
#ifdef ENABLE_MULTI_FOR
#define mrep(it, mr) for(multi_iter it(mr); !it.fin(); ++it)
#endif
template<typename T1, typename T2> inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); }
template<typename T1, typename T2> inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); }
void Yes(bool ok){ std::cout << (ok ? "Yes" : "No") << std::endl; }

map<int, int> submap(const map<int, int> &a, const map<int, int> &b){
    auto a_cp(a);
    for (auto [k, v]: a) {
        if (!b.count(k)) a_cp.erase(k);
    }

    for (auto [k, v]: b) {
        chmin(a_cp[k], v);
    } 

    return a_cp;
}


int main(void){

    int L, R;
    cin >> L >> R;

    map<int, int> mp;
    for (auto p : Eratosthenes::factorize(L)) {
        mp[p.first] += p.second;
    }

    rep(i,L+1,R+1) {
        map<int, int> cur;
        for (auto p : Eratosthenes::factorize(i)) {
            cur[p.first] += p.second;
        }

        mp = submap(mp, cur);
    }

    ll ans = 0;
    for (auto[k, v] : mp) {
        ans += power(k, v);
    }
    cout << ans << endl;


}
yukicoder

結果

テストケース

ソースコード
