結果

問題 No.1164 GCD Products hard
ユーザー kyo1kyo1
提出日時 2021-06-22 14:44:43
言語 C++17
(gcc 12.2.0 + boost 1.81.0)
結果
TLE  
実行時間 -
コード長 6,445 bytes
コンパイル時間 1,896 ms
コンパイル使用メモリ 201,440 KB
実行使用メモリ 42,260 KB
最終ジャッジ日時 2023-09-05 16:15:57
合計ジャッジ時間 36,091 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge11
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1,453 ms
29,944 KB
testcase_01 AC 1,865 ms
32,816 KB
testcase_02 AC 1,146 ms
25,292 KB
testcase_03 AC 338 ms
10,484 KB
testcase_04 AC 261 ms
11,108 KB
testcase_05 AC 1,520 ms
29,512 KB
testcase_06 AC 1,786 ms
35,064 KB
testcase_07 AC 1,819 ms
36,820 KB
testcase_08 AC 1,803 ms
36,476 KB
testcase_09 AC 1,160 ms
26,084 KB
testcase_10 AC 339 ms
10,016 KB
testcase_11 AC 1,196 ms
27,624 KB
testcase_12 AC 2,053 ms
34,804 KB
testcase_13 AC 1,011 ms
22,020 KB
testcase_14 AC 759 ms
25,836 KB
testcase_15 AC 1,878 ms
37,480 KB
testcase_16 AC 961 ms
28,172 KB
testcase_17 AC 1,412 ms
28,556 KB
testcase_18 AC 1,288 ms
26,592 KB
testcase_19 AC 273 ms
11,776 KB
testcase_20 AC 592 ms
15,656 KB
testcase_21 AC 2,186 ms
37,448 KB
testcase_22 AC 2 ms
4,376 KB
testcase_23 AC 1,406 ms
42,224 KB
testcase_24 TLE -
testcase_25 AC 1 ms
4,376 KB
testcase_26 AC 2 ms
4,376 KB
testcase_27 AC 1 ms
4,380 KB
testcase_28 AC 1 ms
4,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

template <typename T>
T inverse(T a, T m) {
  T u = 0, v = 1;
  while (a != 0) {
    T t = m / a;
    m -= t * a;
    u -= t * v;
    std::swap(a, m);
    std::swap(u, v);
  }
  assert(m == 1);
  return u;
}

template <typename T>
class Modular {
 public:
  using Type = std::decay_t<decltype(T::value)>;

  constexpr Modular() : value() {}

  template <typename U>
  Modular(const U &x = 0) : value(normalize(x)) {}

  template <typename U>
  Type normalize(const U &x) {
    Type v;
    if (-mod <= x && x < mod) {
      v = static_cast<Type>(x);
    } else {
      v = static_cast<Type>(x % mod);
    }
    if (v < 0) v += mod;
    return v;
  }

  const Type &operator()() const { return value; }
  template <typename U>
  explicit operator U() const {
    return static_cast<U>(value);
  }
  constexpr static Type mod = T::value;

  Modular &operator+=(const Modular &rhs) {
    if ((value += rhs.value) >= mod) value -= mod;
    return *this;
  }
  Modular &operator-=(const Modular &rhs) {
    if ((value -= rhs.value) < 0) value += mod;
    return *this;
  }

  template <typename U>
  Modular &operator+=(const U &rhs) {
    return *this += Modular(rhs);
  }
  template <typename U>
  Modular &operator-=(const U &rhs) {
    return *this -= Modular(rhs);
  }

  Modular &operator++() { return *this += 1; }
  Modular &operator--() { return *this -= 1; }

  Modular operator++(int) {
    Modular res(*this);
    *this += 1;
    return res;
  }
  Modular operator--(int) {
    Modular res(*this);
    *this -= 1;
    return res;
  }

  template <typename U = T>
  std::enable_if_t<std::is_same<typename Modular<U>::Type, int>::value, Modular> &operator*=(
      const Modular &rhs) {
    value = normalize(static_cast<int64_t>(value) * static_cast<int64_t>(rhs.value));
    return *this;
  }
  template <typename U = T>
  std::enable_if_t<std::is_same<typename Modular<U>::Type, int64_t>::value, Modular> &operator*=(
      const Modular &rhs) {
    value = normalize(static_cast<__int128>(value) * static_cast<__int128>(rhs.value));
    return *this;
  }

  Modular &operator/=(const Modular &rhs) { return *this *= Modular(inverse(rhs.value, mod)); }

  template <typename U>
  friend bool operator==(const Modular<U> &lhs, const Modular<U> &rhs);

  template <typename U>
  friend bool operator<(const Modular<U> &lhs, const Modular<U> &rhs);
  template <typename U>
  friend bool operator>(const Modular<U> &lhs, const Modular<U> &rhs);

  template <typename U>
  friend std::istream &operator>>(std::istream &stream, Modular<U> &rhs);
  template <typename U>
  friend std::ostream &operator<<(std::ostream &stream, const Modular<U> &rhs);

 private:
  Type value;
};

template <typename T>
bool operator==(const Modular<T> &lhs, const Modular<T> &rhs) {
  return lhs.value == rhs.value;
}
template <typename T, typename U>
bool operator==(const Modular<T> &lhs, U rhs) {
  return lhs == Modular<T>(rhs);
}
template <typename T, typename U>
bool operator==(U lhs, const Modular<T> &rhs) {
  return Modular<T>(lhs) == rhs;
}

template <typename T>
bool operator!=(const Modular<T> &lhs, const Modular<T> &rhs) {
  return !(lhs == rhs);
}
template <typename T, typename U>
bool operator!=(const Modular<T> &lhs, U rhs) {
  return !(lhs == rhs);
}
template <typename T, typename U>
bool operator!=(U lhs, const Modular<T> &rhs) {
  return !(lhs == rhs);
}

template <typename T>
bool operator<(const Modular<T> &lhs, const Modular<T> &rhs) {
  return lhs.value < rhs.value;
}

template <typename T>
bool operator>(const Modular<T> &lhs, const Modular<T> &rhs) {
  return lhs.value > rhs.value;
}

template <typename T>
Modular<T> operator+(const Modular<T> &lhs, const Modular<T> &rhs) {
  return Modular<T>(lhs) += rhs;
}
template <typename T, typename U>
Modular<T> operator+(const Modular<T> &lhs, U rhs) {
  return Modular<T>(lhs) += rhs;
}
template <typename T, typename U>
Modular<T> operator+(U lhs, const Modular<T> &rhs) {
  return Modular<T>(lhs) += rhs;
}

template <typename T>
Modular<T> operator-(const Modular<T> &lhs, const Modular<T> &rhs) {
  return Modular<T>(lhs) -= rhs;
}
template <typename T, typename U>
Modular<T> operator-(const Modular<T> &lhs, U rhs) {
  return Modular<T>(lhs) -= rhs;
}
template <typename T, typename U>
Modular<T> operator-(U lhs, const Modular<T> &rhs) {
  return Modular<T>(lhs) -= rhs;
}

template <typename T>
Modular<T> operator*(const Modular<T> &lhs, const Modular<T> &rhs) {
  return Modular<T>(lhs) *= rhs;
}
template <typename T, typename U>
Modular<T> operator*(const Modular<T> &lhs, U rhs) {
  return Modular<T>(lhs) *= rhs;
}
template <typename T, typename U>
Modular<T> operator*(U lhs, const Modular<T> &rhs) {
  return Modular<T>(lhs) *= rhs;
}

template <typename T>
Modular<T> operator/(const Modular<T> &lhs, const Modular<T> &rhs) {
  return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> operator/(const Modular<T> &lhs, U rhs) {
  return Modular<T>(lhs) /= rhs;
}
template <typename T, typename U>
Modular<T> operator/(U lhs, const Modular<T> &rhs) {
  return Modular<T>(lhs) /= rhs;
}

template <typename T, typename U>
Modular<T> pow(const Modular<T> &a, const U &b) {
  assert(b >= 0);
  Modular<T> x = a, res = 1;
  U n = b;
  while (n > 0) {
    if (n & 1) res *= x;
    x *= x;
    n >>= 1;
  }
  return res;
}

template <typename T>
std::istream &operator>>(std::istream &stream, Modular<T> &rhs) {
  typename std::common_type<typename Modular<T>::Type, int64_t>::type x;
  stream >> x;
  rhs = Modular<T>(x);
  return stream;
}

template <typename T>
std::ostream &operator<<(std::ostream &stream, const Modular<T> &rhs) {
  stream << rhs.value;
  return stream;
}

constexpr int mod = 1000000007;
// constexpr int mod = 998244353;
using mint = Modular<std::integral_constant<std::decay_t<decltype(mod)>, mod>>;
constexpr int mod2 = 1000000006;
using mint2 = Modular<std::integral_constant<std::decay_t<decltype(mod2)>, mod2>>;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int A, B, N;
  cin >> A >> B >> N;
  vector<mint2> X(B + 1, 0);
  for (int g = B; g > 0; g--) {
    int a = (A - 1) / g, b = B / g;
    X[g] = pow(static_cast<mint2>(b - a), N);
    for (int i = 2 * g; i < B + 1; i += g) {
      X[g] -= X[i];
    }
  }
  mint res = 1;
  for (int i = 1; i < B + 1; i++) {
    res *= pow(static_cast<mint>(i), X[i]());
  }
  cout << res << '\n';
  return 0;
}
0