結果

問題 No.1351 Sum of GCD Equals LCM
コンテスト
ユーザー ibylog
提出日時 2021-01-17 15:20:57
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 8,248 bytes
コンパイル時間 1,681 ms
コンパイル使用メモリ 179,400 KB
実行使用メモリ 6,824 KB
最終ジャッジ日時 2024-11-29 17:41:54
合計ジャッジ時間 10,732 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other WA * 50
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
#define input_fast ios::sync_with_stdio(0); cin.tie(0);cout.tie(0)
#define two_int pair<int, int>
#define X first
#define Y second
#define rep(i,n) for(int i=0;i<(n);i++)
#define rep1(i,n) for(int i=1;i<=(n);i++)
#define rrep(i,n) for(int i=(n)-1;i>=0;i--)
#define rrep1(i,n) for(int i=(n);i>0;i--)
#define REP(i,a,b) for(int i=a;i<b;i++)
#define ALL(a) a.begin(),a.end()
#define each(e,v) for(auto& e : v)
#define print(a) cout << (a) << endl
#define printP(a) cout << setprecision(15) <<fixed << (a) << endl
#define elif else if
#define len(X) ((int)(X).size())

const int INF = 1e18;
const double pi = 3.14159265358979323846;
const int dx[4] = { 1, 0, -1, 0 };
const int dy[4] = { 0, 1, 0, -1 };

template<class T = int> using P = pair<T,T>;
template<class T = int> using Array = vector<T>;
template<class T = int> using Matrix = Array< Array<T> >;
template<class T> using heapq = priority_queue<T, vector<T>, greater<T>>;
template<class T> using heapQ = priority_queue<T, vector<T>, greater<T>>;
template<class T1,class T2>ostream& operator<<(ostream& os,const pair<T1,T2>&a){return os<<"("<<a.first<<","<<a.second<< ")";}
template<class T> ostream& operator << (ostream &s, vector<T> &P)
{ for (int i = 0; i < P.size(); ++i) { if (i > 0) { s << " "; } s << P[i]; } return s; }
template<class T1, class T2> ostream& operator << (ostream &s, map<T1,T2> &P)
{ for(auto it : P) { s << "<" << it.first << "->" << it.second << "> "; } return s; }
template <class T>bool chmax(T &a, T b){if (a < b){a = b;return true;}return false;}
template <class T>bool chmin(T &a, T b){if (a > b){a = b;return true;}return false;}
template <class T>T gcd(T a, T b){return (b == 0) ? a : gcd(b, a % b);}
template <class T>T lcm(T a, T b){return a / gcd(a, b) * b;}

template<int MOD> struct Fp {
    //非型テンプレートパラメタ
    int val;

    constexpr Fp(int v = 0) noexcept : val(v % MOD) {
        if (val < 0) val += MOD;
    }

    constexpr int getmod() { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0;
    }

    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }

    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }

    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }

    constexpr Fp& operator /= (const Fp& r) noexcept {
        int a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            int t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }

    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }

    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }

    friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }

    friend constexpr Fp<MOD> modpow(const Fp<MOD> &a,int n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};

struct Graph
{
    struct Edge
    {
        int dst;
        int weight;
        Edge(int dst, int weight) : dst(dst), weight(weight) {}
    };
    vector<vector<Edge>> G;
    vector<int> depth;
    vector<pair<int,int>> EDGE;
    int N;
    Graph(int n){
        G = vector<vector<Edge>>(n + 1,vector<Edge>{});
        depth = vector<int>(n + 1, -1);
        EDGE = vector<pair<int,int>>{};
        N = n;
    }

    void dijkstra(int S,vector<int> &D){
        D.assign(D.size(),INF);
        D[S] = 0;
        priority_queue<two_int,vector<two_int>,greater<two_int>> Q;
        Q.push(two_int(0,S));
        while (!Q.empty()){
            auto v = Q.top();
            int d = v.first;
            int node = v.second;
            Q.pop();
            if (D[node]<d){continue;}
            for (auto v:G[node]){auto dst = v.dst,weight = v.weight;
                if (D[dst] > weight + d){D[dst] = weight + d;Q.push(two_int(D[dst],dst));}
            }
        }
    }
    void dfs(int S){
        if (depth[S] < 0){depth[S] = 0;}
        for (auto v:G[S]){auto dst = v.dst,weight = v.weight;
            if (depth[dst] < 0){depth[dst] =depth[S] + 1;dfs(dst);}
        }
    }
    void clean(){
        depth.assign(N,-1);
    }
    void add_edge(int x,int y,int weight = 1){
        G[x].push_back(Edge{y,weight});
        G[y].push_back(Edge{x,weight});
        EDGE.push_back(two_int{x,y});
    }
};
class UnionFind
{
public:
    vector<int> par; // 各元の親を表す配列
    vector<int> siz; // 素集合のサイズを表す配列(1 で初期化)
    UnionFind(int sz_) : par(sz_), siz(sz_, 1)
    {
        for (int i = 0; i < sz_; ++i)
            par[i] = i;
    }
    void init(int sz_)
    {
        par.resize(sz_);
        siz.assign(sz_, 1LL);
        for (int i = 0; i < sz_; ++i)
            par[i] = i;
    }

    int root(int x)
    {
        while (par[x] != x)
        {
            x = par[x] = par[par[x]];
        }
        return x;
    }

    bool merge(int x, int y)
    {
        x = root(x);
        y = root(y);
        if (x == y)
            return false;
        if (siz[x] < siz[y])
            swap(x, y);
        siz[x] += siz[y];
        par[y] = x;
        return true;
    }

    bool same(int x, int y)
    {
        return root(x) == root(y);
    }

    int size(int x)
    {
        return siz[root(x)];
    }
};

class BIT
{
public:
    vector<int> bit;
    int M;

    BIT(int M) : bit(vector<int>(M + 1, 0)), M(M) {}

    int sum(int i)
    {
        if (!i)
            return 0;
        if (i == 0)
            return 0;
        return bit[i] + sum(i - (i & -i));
    }

    void change(int i, int x)
    {
        if (i > M)
            return;
        bit[i] = x;
        change(i + (i & -i), x);
    }
    int query(int l, int r)
    {
        //[l,r]
        return sum(r) - sum(l - 1);
    }
};

struct Eratos {
    vector<int> primes;
    vector<bool> isprime;
    vector<int> min_factor;

    Eratos(int MAX) : primes(),
                      isprime(MAX+1, true),
                      min_factor(MAX+1, -1) {
        isprime[0] = isprime[1] = false;
        min_factor[0] = 0, min_factor[1] = 1;
        for (int i = 2; i <= MAX; ++i) {
            if (!isprime[i]) continue;
            primes.push_back(i);
            min_factor[i] = i;
            for (int j = i*2; j <= MAX; j += i) {
                isprime[j] = false;
                if (min_factor[j] == -1) min_factor[j] = i;
            }
        }
    }

    // prime factorization
    vector<pair<int,int>> prime_factorize(int n) {
        vector<pair<int,int> > res;
        while (n != 1) {
            int prime = min_factor[n];
            int exp = 0;
            while (min_factor[n] == prime) {
                ++exp;
                n /= prime;
            }
            res.push_back(make_pair(prime, exp));
        }
        return res;
    }
};

int gcd(int a, int b) {
  return b != 0 ? gcd(b, a % b) : a;
}
int lcm(int a, int b) {
  return a * b / gcd(a, b);
}
// a x + b y = gcd(a, b)
int extgcd(int a, int b, int &x, int &y) {
  int g = a; x = 1; y = 0;
  if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
  return g;
}

int invMod(int a, int m) {
  int x, y;
  if (extgcd(a, m, x, y) == 1) return (x + m) % m;
  else                         return -1; // unsolvable
}
signed main(){
    input_fast;
    Eratos PRIMES(10000);
    int N;cin>>N;
    Array<int> A(N);
    A[0] = 1;
    rep1(i,N - 1){A[i]= PRIMES.primes[i];}
    print(A);
    return 0;
}
0