結果

問題 No.1529 Constant Lcm
コンテスト
ユーザー Ogtsn99
提出日時 2021-06-04 22:10:55
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 6,320 bytes
コンパイル時間 2,423 ms
コンパイル使用メモリ 208,492 KB
最終ジャッジ日時 2025-01-22 01:20:57
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 9 TLE * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define rep(i, n) for(int (i)=0;(i)<(n);(i)++)
#define rrep(i, n) for(int (i)=((n)-1);(i)>=0;(i)--)
#define itn int
#define miele(v) min_element(v.begin(), v.end())
#define maele(v) max_element(v.begin(), v.end())
#define SUM(v) accumulate(v.begin(), v.end(), 0LL)
#define lb(a, key) lower_bound(a.begin(),a.end(),key)
#define ub(a, key) upper_bound(a.begin(),a.end(),key)
#define COUNT(a, key) count(a.begin(), a.end(), key)
#define BITCOUNT(x) __builtin_popcount(x)
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define F first
#define S second
using P = pair<int, int>;
using WeightedGraph = vector<vector<P>>;
using UnWeightedGraph = vector<vector<int>>;
using Real = long double;
using Point = complex<Real>; //Point and Vector2d is the same!
// p.real() or real(p) -> x軸, p.imag() or imag(p) -> y軸
using Vector2d = complex<Real>;
const int MOD = 998244353;
const long long INF = 1LL << 60;
const double EPS = 1e-15;
const double PI = 3.14159265358979323846;

template<typename T>
int getIndexOfLowerBound(vector<T> &v, T x) {
    return lower_bound(v.begin(), v.end(), x) - v.begin();
}

template<typename T>
int getIndexOfUpperBound(vector<T> &v, T x) {
    return upper_bound(v.begin(), v.end(), x) - v.begin();
}

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;
}

#define repi(itr, ds) for (auto itr = ds.begin(); itr != ds.end(); itr++)

istream &operator>>(istream &is, Point &p) {
    Real a, b;
    is >> a >> b;
    p = Point(a, b);
    return is;
}

template<typename T, typename U>
istream &operator>>(istream &is, pair<T, U> &p_var) {
    is >> p_var.first >> p_var.second;
    return is;
}

template<typename T>
istream &operator>>(istream &is, vector<T> &vec) {
    for (T &x : vec) is >> x;
    return is;
}

template<typename T, typename U>
ostream &operator<<(ostream &os, pair<T, U> &pair_var) {
    os << pair_var.first << ' ' << pair_var.second;
    return os;
}

template<typename T>
ostream &operator<<(ostream &os, vector<T> &vec) {
    for (int i = 0; i < vec.size(); i++)
        os << vec[i] << ' ';
    return os;
}

template<typename T, typename U>
ostream &operator<<(ostream &os, vector<pair<T, U>> &vec) {
    for (int i = 0; i < vec.size(); i++)
        os << vec[i] << '\n';
    return os;
}

template<typename T>
ostream &operator<<(ostream &os, vector<vector<T>> &df) {
    for (auto &vec : df) os << vec;
    return os;
}

template<typename T, typename U>
ostream &operator<<(ostream &os, map<T, U> &map_var) {
    repi(itr, map_var) {
        os << *itr << ' ';
        itr++;
        itr--;
    }
    return os;
}

template<typename T>
ostream &operator<<(ostream &os, set<T> &set_var) {
    repi(itr, set_var) {
        os << *itr << ' ';
        itr++;
        itr--;
    }
    return os;
}

void print() { cout << endl; }

template<class Head, class... Tail>
void print(Head &&head, Tail &&... tail) {
    cout << head;
    if (sizeof...(tail) != 0) cout << " ";
    print(forward<Tail>(tail)...);
}

long long gcd(long long a,long long b)
{
    if (a%b==0) return(b);
    else return(gcd(b,a%b));
}
long long lcm(long long a,long long b){
long long g = gcd(a,b);
return a / g * b;
}

struct Miller{
    const vector<long long> v = { 2 , 7 , 61 }; // < 4,759,123,141
    // x^k (mod m)
    long long modpow( long long x, long long k, long long m ){
        long long res = 1;
        while( k ){
            if( k & 1 ){
                res = res * x % m;
            }
            k /= 2;
            x = x * x % m;
        }
        return res;
    }
    // check if n is prime
    bool check( long long n ){
        if( n < 2 ){
            return false;
        }
        long long d = n - 1;
        long long s = 0;
        while( d % 2 == 0 ){
            d /= 2;
            s++;
        }
        for( long long a : v ){
            if( a == n ){
                return true;
            }
            if( modpow( a , d , n ) != 1 ){
                bool ok = true;
                for( long long r = 0; r < s; r++ ){
                    if( modpow( a, d * (1LL << r), n ) == n-1 ){
                        ok = false;
                        break;
                    }
                }
                if( ok ){
                    return false;
                }
            }
        }
        return true;
    }
};

struct Rho{
    mt19937 mt;
    Miller miller;
    long long c;
    Rho(){
        mt.seed( clock() );
    }
    inline long long f( long long x, long long n ){
        return ( x * x + c ) % n;
    }
    long long check( long long n ){
        if( n == 4 ){
            return 2;
        }
        c = mt() % n;
        long long x = mt() % n;
        long long y = x;
        long long d = 1;
        while( d == 1 ){
            x = f(x, n);
            y = f(f(y,n),n);
            d = gcd( abs(x-y), n );
        }
        if( d == n ){
            return -1;
        }
        return d;
    }
    vector<long long> factor( long long n ){
        if( n <= 1 ){
            return {};
        }
        if( miller.check( n ) ){
            return { n };
        }
        long long res = -1;
        while( res == -1 ){
            res = check( n );
        }
        vector<long long> fa = factor( res );
        vector<long long> fb = factor( n / res );
        fa.insert( fa.end() , fb.begin(), fb.end() );
        return fa;
    }
};

Rho rho;

int mpow(int x, int n) {
  int ret = 1;
  while(n > 0) {
    if(n & 1) (ret *= x) %= MOD;
    (x *= x) %= MOD;
    n >>= 1;
  }
  return ret;
}

signed main(void) { cin.tie(0); ios::sync_with_stdio(false);
    int n; cin>>n;
    int cnt = 1;
    map <int, int> ma;

    for (int i = n-1; i >= 1; --i) {
        int num = cnt*i;
        auto tmp = rho.factor(num);

        map<int, int> ma_tmp;
        for (int j = 0; j < tmp.size(); ++j) {
            ma_tmp[tmp[j]]++;
        }
        for (auto p : ma_tmp) {
            chmax(ma[p.F], p.S);
        }
        cnt++;
    }

    int ans = 1;
    for (auto p : ma) {
        ans *= mpow(p.F, p.S);
        ans %= MOD;
    }
    print(ans);
}
0