結果

問題 No.1396 Giri
ユーザー RedSpica
提出日時 2021-02-14 22:09:14
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 269 ms / 2,000 ms
コード長 4,556 bytes
コンパイル時間 1,257 ms
コンパイル使用メモリ 109,000 KB
実行使用メモリ 26,752 KB
最終ジャッジ日時 2024-07-22 09:51:17
合計ジャッジ時間 5,747 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<algorithm>
#include<math.h>
#include<string>
#include<tuple>
#include<vector>
#include<cstdlib>
#include<cstdint>
#include<stdio.h>
#include<cmath>
#include<limits>
#include<iomanip> 
#include<ctime>
#include<climits>
#include<random>
#include<queue>
#include<map>
#include<time.h>


using namespace std;

template <class T> using V = vector<T>;

template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}

const long long INF = 1LL << 60;
const double pi=acos(-1);

using ll = long long;
using vll = V<ll>;
using vvll = V<V<ll>>;
using vpll =V<pair<ll,ll>>;
using graph = V<V<ll>>;


#define FOR(i,a,b) for(ll i=(a);i<(b);i++)
#define bgn begin()
#define en end()
#define SORT(a) sort((a).bgn,(a).en)
#define REV(a) reverse((a).bgn,(a).en)
#define fi first
#define se second
#define gcd(a,b) __gcd(a,b)
#define ALL(a)  (a).begin(),(a).end()


template<typename T>
std::vector<T> make_vec(size_t n){
  return std::vector<T>(n);
}

template<typename T, class... Args>
auto make_vec(size_t n, Args... args){
  return std::vector<decltype(make_vec<T>(args...))>(n,make_vec<T>(args...));
}


const int MAX = 5100000;
// change
//const int MOD = 1000000007;
const int MOD=998244353;

long long fac[MAX], finv[MAX], inv[MAX];

void Comuse() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for (int i = 2; i < MAX; i++){
    fac[i] = fac[i - 1] * i % MOD;
    inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;
    finv[i] = finv[i - 1] * inv[i] % MOD;
  }
}


#define comuse Comuse()

ll combi(int n, int k){
  if (n < k) return 0;
  if (n < 0 || k < 0) return 0;
  return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;
}

ll perm(int n,int k){
  if(n < k) return 0;
  if(n < 0 || k < 0) return 0;
  return fac[n] * (finv[k] % MOD) % MOD;
}

ll modpow(ll a,ll n,ll mod){
  ll ans=1;
  while(n>0){
    if(n&1){
      ans=ans*a%mod;
    }

    a=a*a%mod;
    n/=2;
  }

  return ans;
}

ll POW(ll a,ll n){
  ll ans=1;
  while(n>0){
    if(n&1){
      ans=ans*a;
    }

    a=a*a;
    n/=2;
  }

  return ans;
}

ll modinv(ll a, ll mod) {
    return modpow(a, mod - 2, mod);
}

ll modcombi(int n,int k,int mod){
  ll ans=1;
  for(ll i=n;i>n-k;i--){
    ans*=i;
    ans%=mod;
  }
  for(ll i=1;i<=k;i++){
    ans*=modinv(i,mod);
    ans%=mod;
  }

  return ans;
}


vll div(ll n){
  vll ret;
  for(ll i=1;i*i<=n;i++){
    if(n%i==0){
      ret.push_back(i);
      if(i*i!=n){
        ret.push_back(n/i);
      }
    }
  }
  SORT(ret);
  return (ret);
}


const int era=2000000;
long long sieve[era];

void Sieveuse(){
  for(ll i=1;i<era;i++){
    sieve[i]=i;
  }

  for(ll i=2;i<era;i++){
    for(ll j=2*i;j<era;j+=i){
      chmin(sieve[j],i);
    }
  }
}

bool isprime(int p){
  if(sieve[p]==p){
    return true;
  }
  else{
    return false;
  }
}

ll lcm(ll a,ll b){
  return a/gcd(a,b)*b;
}

void bf(ll n,string s){
  for(ll i=0;i<n;i++){
    cout<<s;
  }
  cout<<"\n";

  return;
}

long long extGCD(long long a, long long b, long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    long long d = extGCD(b, a%b, y, x);
    y -= a/b * x;
    return d;
}






void Solve();


const int MAX_N = 131072;
//segment tree 
int NN;
int seg[MAX_N*2-1];
void seguse(){
  for(int i=0;i<2*NN-1;i++){
    seg[i]=INT_MAX;
  }
}



signed main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout<<setprecision(20)<<fixed;
  Solve();
}


/****************************************\
| Thank you for viewing my code:)        |
| Written by RedSpica a.k.a. RanseMirage |
| Twitter:@asakaakasaka                  | 
\****************************************/
//segtreeの葉の先頭の添え字はN-1

void Solve(){
  Sieveuse();
  ll n;
    cin>>n;
  ll pos=n;
  while(true){
    if(isprime(pos)){
      break;
    }
    else{
      pos--;
    }
  }

  vll A(n+1);

  FOR(i,2,n+1){
    vll X(0);
    if(i==pos){
      continue;
    }

    ll now=i;
    
    while(now>1){
      X.push_back(sieve[now]);
      now/=sieve[now];
    }
    
    
    

    ll m=X.size();
    ll cnt=1;

    



    FOR(j,1,m){
      if(X[j-1]==X[j]){
        cnt++;
      }
      else{
        ll x=X[j-1];
        chmax(A[x],cnt);
        cnt=1;
      }
      
    }
    chmax(A[X[m-1]],cnt);
  }
    


  ll ans=1;

  FOR(i,2,n+1){
    ans*=modpow(i,A[i],MOD);
    ans%=MOD;
  }

  cout<<ans<<"\n";

  return;
}
0