結果

問題 No.1164 GCD Products hard
ユーザー firiexpfiriexp
提出日時 2020-11-27 18:54:15
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 2,225 ms / 2,500 ms
コード長 4,431 bytes
コンパイル時間 1,501 ms
コンパイル使用メモリ 110,436 KB
実行使用メモリ 45,252 KB
最終ジャッジ日時 2024-07-23 21:41:50
合計ジャッジ時間 33,517 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,273 ms
32,952 KB
testcase_01 AC 1,699 ms
36,164 KB
testcase_02 AC 1,180 ms
28,340 KB
testcase_03 AC 339 ms
13,756 KB
testcase_04 AC 329 ms
14,232 KB
testcase_05 AC 1,374 ms
32,656 KB
testcase_06 AC 1,659 ms
38,132 KB
testcase_07 AC 1,664 ms
39,832 KB
testcase_08 AC 1,524 ms
39,624 KB
testcase_09 AC 1,095 ms
29,544 KB
testcase_10 AC 353 ms
13,032 KB
testcase_11 AC 1,264 ms
30,944 KB
testcase_12 AC 1,740 ms
37,992 KB
testcase_13 AC 972 ms
25,452 KB
testcase_14 AC 886 ms
29,088 KB
testcase_15 AC 1,689 ms
40,500 KB
testcase_16 AC 1,051 ms
31,120 KB
testcase_17 AC 1,394 ms
31,988 KB
testcase_18 AC 1,199 ms
29,644 KB
testcase_19 AC 371 ms
14,748 KB
testcase_20 AC 619 ms
18,768 KB
testcase_21 AC 1,935 ms
40,600 KB
testcase_22 AC 37 ms
6,944 KB
testcase_23 AC 1,617 ms
45,136 KB
testcase_24 AC 2,225 ms
45,252 KB
testcase_25 AC 39 ms
6,940 KB
testcase_26 AC 39 ms
6,944 KB
testcase_27 AC 38 ms
6,940 KB
testcase_28 AC 38 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <numeric>
#include <bitset>
#include <cmath>

static const int MOD = 1000000007;
using ll = long long;
using u32 = unsigned;
using u64 = unsigned long long;
using namespace std;

template<class T> constexpr T INF = ::numeric_limits<T>::max() / 32 * 15 + 208;

template <u32 M>
struct modint {
    u32 val;
public:
    static modint raw(int v) { modint x; x.val = v; return x; }
    modint() : val(0) {}
    template <class T>
    modint(T v) { ll x = (ll)(v%(ll)(M)); if (x < 0) x += M; val = u32(x); }
    modint(bool v) { val = ((unsigned int)(v) % M); }
    modint& operator++() { val++; if (val == M) val = 0; return *this; }
    modint& operator--() { if (val == 0) val = M; val--; return *this; }
    modint operator++(int) { modint result = *this; ++*this; return result; }
    modint operator--(int) { modint result = *this; --*this; return result; }
    modint& operator+=(const modint& b) { val += b.val; if (val >= M) val -= M; return *this; }
    modint& operator-=(const modint& b) { val -= b.val; if (val >= M) val += M; return *this; }
    modint& operator*=(const modint& b) { u64 z = val; z *= b.val; val = (u32)(z % M); return *this; }
    modint& operator/=(const modint& b) { return *this = *this * b.inv(); }
    modint operator+() const { return *this; }
    modint operator-() const { return modint() - *this; }
    modint pow(long long n) const { modint x = *this, r = 1; while (n) { if (n & 1) r *= x; x *= x; n >>= 1; } return r; }
    modint inv() const { return pow(M-2); }
    friend modint operator+(const modint& a, const modint& b) { return modint(a) += b; }
    friend modint operator-(const modint& a, const modint& b) { return modint(a) -= b; }
    friend modint operator*(const modint& a, const modint& b) { return modint(a) *= b; }
    friend modint operator/(const modint& a, const modint& b) { return modint(a) /= b; }
    friend bool operator==(const modint& a, const modint& b) { return a.val == b.val; }
    friend bool operator!=(const modint& a, const modint& b) { return a.val != b.val; }
};
using mint = modint<MOD-1>;
using mint2 = modint<MOD>;

struct Prime { // Wheel factorization
    static constexpr int wheel[] = {4, 2, 4, 2, 4, 6, 2, 6},
            wheel2[] = {7, 11, 13, 17, 19, 23, 29, 31},
            wheel_sum[] = {0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7, 7};
    static inline int f(int n){ return (n-1)/30*8 + wheel_sum[(n-1)%30]; }
    static inline int g(int n){ return ((n-1) >> 3)*30 + wheel2[(n-1)&7]; }
    vector<int> primes;

    Prime(int M) {
        primes = {2, 3, 5};
        if(M < 7){
            while(!primes.empty() && M < primes.back()) primes.pop_back();
            return;
        }
        int n = f(M), m = g(n), k = f(int(floor(sqrt(M))));
        primes.reserve(3+max(0, (int)(n/(log(n)-1.12))));
        vector<bool> sieve(n+1, true);
        for (int i = 1; i <= k; ++i) {
            if(sieve[i]){
                ll p = g(i), q = p*p;
                int j = (i-1)&7;
                while(q <= m){
                    sieve[f(q)] = false;
                    q += wheel[j] * p;
                    j = (j+1)&7;
                }
            }
        }
        for (int i = 1; i <= n; ++i) {
            if(sieve[i]) primes.emplace_back(g(i));
        }
    }
};
constexpr int Prime::wheel[], Prime::wheel2[], Prime::wheel_sum[];
Prime p(10000010);
template<class T>
void div_transform(vector<T> &a){
    int n = a.size();
    for (auto &&i : p.primes) {
        if(i >= n) break;
        for (int k = (n-1)/i; k > 0; --k) {
            a[k] += a[k*i];
        }
    }
    for (int i = 1; i < n; ++i) a[i] += a[0];
}
template<class T>
void div_itransform(vector<T> &a){
    int n = a.size();
    for (int i = 1; i < n; ++i) a[i] -= a[0];
    for (auto &&i : p.primes) {
        if(i >= n) break;
        for (int k = 1; k*i < n; ++k) {
            a[k] -= a[k*i];
        }
    }
}

int main() {
    int a, b, n;
    cin >> a >> b >> n;
    vector<mint> v(b+1);
    for (int i = a; i <= b; ++i) {
        v[i] = 1;
    }
    div_transform(v);
    for (int i = 1; i <= b; ++i) {
        v[i] = v[i].pow(n);
    }
    div_itransform(v);
    mint2 ans = 1;
    for (int i = 2; i <= b; ++i) {
        ans *= mint2(i).pow(v[i].val);
    }
    printf("%d\n", ans.val);
    return 0;
}
0