結果

問題 No.1396 Giri
コンテスト
ユーザー sash2104
提出日時 2021-02-14 21:42:20
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 508 ms / 2,000 ms
コード長 5,177 bytes
コンパイル時間 1,910 ms
コンパイル使用メモリ 186,460 KB
実行使用メモリ 11,276 KB
最終ジャッジ日時 2024-07-22 09:11:03
合計ジャッジ時間 6,824 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define ALL(x) std::begin(x), std::end(x)
using namespace std;
// @title mod int
#include <iostream>
using ll = long long;
// @title 素数判定、素因数分解
#include <cassert>
#include <iostream>
#include <vector>
#include <map>

using ll = long long;

class Prime {
// n以下の素数を列挙する
public:
  const int n;
  std::vector<bool> is_prime;
  std::vector<int> primes;
  Prime(int size) : n(size), is_prime(n+1, true) {
    is_prime[0] = false;
    is_prime[1] = false;
    for (int i = 2; i <= n; ++i) {
      if (!is_prime[i]) continue;
      primes.push_back(i);
      int tmp = 2*i;
      while (tmp <= n) {
        is_prime[tmp] = false;
        tmp += i;
      }
    }
  }

  bool check(int x) { return is_prime[x]; }
};

struct PrimeFactorization {
  // n*n以下の数についての素因数分解
  const int n;
  Prime p;
  PrimeFactorization(int n) : n(n), p(n) {}

  std::map<ll, int> calc(ll a) {
    std::map<ll, int> ret;
    ll tmp = a;
    for (int i: p.primes) {
      if (i > tmp) break;
      int count = 0;
      while (tmp % i == 0) { 
        ++count;
        tmp /= i;
      }
      if (count > 0) ret[i] = count;
    }
    if (tmp > 1) ret[tmp] = 1;
    return ret;
  }
};

struct FastPrimeFactorization {
  /**
   * @brief n以下の数について高速で、n*n以下の数で普通に素因数分解を行う
   * 
   */
  int n;
  std::vector<int> divides; // その数を割り切る最小の素因数
  std::vector<int> primes; // n以下の素数
  FastPrimeFactorization(int n) : n(n), divides(n+1) {
    assert(n <= 2000000);
    // エラトステネスの篩にかけ、最小の素因数をdividesに書き込んでいく
    for (int i = 2; i <= n; ++i) {
      if (divides[i] > 0) continue;
      primes.push_back(i);
      int j = i;
      while (j <= n) {
        if (divides[j] == 0) {
          divides[j] = i;
        }
        j += i;
      }
    }
    // for (int i = 0; i <= n; ++i) { 
    //   cout << i << " " << divides[i] << endl;
    // }
  }

  std::map<ll, int> calc(ll a) {
    std::map<ll, int> ret;
    // 高速に計算できない部分は愚直にやる
    ll tmp = a;
    for (int i: primes) {
      if (tmp <= n || i > tmp) break;
      int count = 0;
      while (tmp % i == 0) { 
        ++count;
        tmp /= i;
      }
      if (count > 0) ret[i] = count;
    }
    if (tmp > n) {
      // nより大きい素数
      ret[tmp] = 1;
      return ret;
    }
    while (tmp > 1) {
      int d = divides[tmp];
      ++ret[d];
      tmp /= d;
    }
    return ret;
  }
};

#if 0
using namespace std;
int main() {
  FastPrimeFactorization pf(1000000);
  // PrimeFactorization pf(1000000);
  std::map<ll, int> factors;


  ll a = (ll)2*2*5*7*7*41;
  factors = pf.calc(a);
  cout << "prime factors of " << a << " is ..." << endl;
  for (auto it : factors) { 
    cout << it.first << " " << it.second << endl;
  }
  cout << endl;

  // 最大数付近での確認
  a = (ll)999983*999983;
  factors = pf.calc(a);
  cout << "prime factors of " << a << " is ..." << endl;
  for (auto it : factors) { 
    cout << it.first << " " << it.second << endl;
  }
}
#endif

#ifdef MUTABLE
int mod;
#else
template<int mod>
#endif
struct ModInt {
  int val;
  ModInt inv() const{
    int tmp,a=val,b=mod,x=1,y=0;
    while(b)tmp=a/b,a-=tmp*b,std::swap(a,b),x-=tmp*y,std::swap(x,y);
    return ModInt(x);
  }
  ModInt():val(0){}
  ModInt(ll x){if((val=x%mod)<0)val+=mod;}
  ModInt pow(ll t){ModInt res=1,b=*this; while(t){if(t&1)res*=b;b*=b;t>>=1;}return res;}
  ModInt& operator+=(const ModInt& x){if((val+=x.val)>=mod)val-=mod;return *this;}
  ModInt& operator-=(const ModInt& x){if((val+=mod-x.val)>=mod)val-=mod; return *this;}
  ModInt& operator*=(const ModInt& x){val=(ll)val*x.val%mod; return *this;}
  ModInt& operator/=(const ModInt& x){return *this*=x.inv();}
  bool operator==(const ModInt& x) const{return val==x.val;}
  bool operator!=(const ModInt& x) const{return val!=x.val;}
  bool operator<(const ModInt& x) const{return val<x.val;}
  bool operator<=(const ModInt& x) const{return val<=x.val;}
  bool operator>(const ModInt& x) const{return val>x.val;}
  bool operator>=(const ModInt& x) const{return val>=x.val;}
  ModInt operator+(const ModInt& x) const{return ModInt(*this)+=x;}
  ModInt operator-(const ModInt& x) const{return ModInt(*this)-=x;}
  ModInt operator*(const ModInt& x) const{return ModInt(*this)*=x;}
  ModInt operator/(const ModInt& x) const{return ModInt(*this)/=x;}
  friend std::ostream& operator<<(std::ostream& os, const ModInt& mi) { os << mi.val; return os; }
  static int get_mod() { return mod; }
};

#ifndef MUTABLE
using modint = ModInt<998244353>;
#endif
int main() {
    FastPrimeFactorization pf(1000001);
    int n; cin >> n;
    std::map<int, int> all;
    modint ans = 1;
    ll m = 0;
    for (int i = 1; i <= n; ++i) {
      std::map<ll, int> factors = pf.calc(i);
      for (auto it: factors) {
        all[it.first] = max(all[it.first], it.second);
        m = max(m, it.first);
      }
    }
    for (auto it: all) {
      ans *= modint(it.first).pow(it.second);
    }
    ans /= m;
    cout << ans << endl;

    return 0;
}
0