結果

問題 No.2380 Sylow P-subgroup
コンテスト
ユーザー _____TAB_____
提出日時 2023-07-15 13:04:39
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 25 ms / 2,000 ms
コード長 2,250 bytes
コンパイル時間 639 ms
コンパイル使用メモリ 68,092 KB
最終ジャッジ日時 2025-02-15 14:58:03
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 14
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
using namespace std;

#include <iostream>
#include <cassert>

template<long long mod>
class modint{
private:
  using T = long long;
  T a;
public:
  constexpr modint(const long long x = 0) noexcept : a((x%mod+mod)%mod) {}
  constexpr T& value() noexcept { return a; }
  constexpr const T& value() const noexcept { return a; }
  constexpr modint operator-() const noexcept {
    return modint(0) -= *this;
  }
  constexpr modint operator+(const modint& rhs) const noexcept {
    return modint(*this) += rhs;
  }
  constexpr modint operator-(const modint& rhs) const noexcept {
    return modint(*this) -= rhs;
  }
  constexpr modint operator*(const modint& rhs) const noexcept {
    return modint(*this) *= rhs;
  }
  constexpr modint operator/(const modint& rhs) const noexcept {
    return modint(*this) /= rhs;
  }
  constexpr modint& operator+=(const modint& rhs) noexcept {
    a += rhs.a;
    if(a >= mod) a -= mod;
    return *this;
  }
  constexpr modint& operator-=(const modint& rhs) noexcept {
    if(a < rhs.a) a += mod;
    a -= rhs.a;
    return *this;
  }
  constexpr modint& operator*=(const modint& rhs) noexcept {
    a = a*rhs.a%mod;
    return *this;
  }
  constexpr modint& operator/=(const modint& rhs) noexcept {
    return *this *= rhs.inv();
  }
  constexpr bool operator==(const modint& rhs) const noexcept {
    return a == rhs.a;
  }
  constexpr bool operator!=(const modint& rhs) const noexcept {
    return not (*this == rhs);
  }
  constexpr modint pow(long long k) const noexcept {
    modint ret(1);
    modint x = k > 0 ? *this : this->inv();
    k = abs(k);
    while(k > 0){
      if(k&1) ret *= x;
      x *= x;
      k >>= 1;
    }
    return ret;
  }
  constexpr modint inv() const noexcept {
    return pow(mod-2);
  }
  friend std::ostream& operator<<(std::ostream &os, const modint &X) noexcept {
    return os << X.a;
  }
  friend std::istream& operator>>(std::istream &is, modint &X) noexcept {
    is >> X.a;
    X.a %= mod;
    if(X.a < 0) X.a += mod;
    return is;
  }
};

int main(){
  using mint = modint<998244353>;
  long long n, p;
  cin >> n >> p;
  long long q = 1;
  long long cnt = 0;
  while(q <= n/p){
    q *= p;
    cnt += n/q;
  }
  cout << mint(p).pow(cnt) << '\n';
}
0