結果
問題 | No.1351 Sum of GCD Equals LCM |
ユーザー | ibylog |
提出日時 | 2021-01-17 15:20:57 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 8,248 bytes |
コンパイル時間 | 1,778 ms |
コンパイル使用メモリ | 179,868 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-05-07 04:32:45 |
合計ジャッジ時間 | 10,917 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | WA | - |
testcase_01 | WA | - |
testcase_02 | WA | - |
testcase_03 | WA | - |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
testcase_17 | WA | - |
testcase_18 | WA | - |
testcase_19 | WA | - |
testcase_20 | WA | - |
testcase_21 | WA | - |
testcase_22 | WA | - |
testcase_23 | WA | - |
testcase_24 | WA | - |
testcase_25 | WA | - |
testcase_26 | WA | - |
testcase_27 | WA | - |
testcase_28 | WA | - |
testcase_29 | WA | - |
testcase_30 | WA | - |
testcase_31 | WA | - |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | WA | - |
testcase_35 | WA | - |
testcase_36 | WA | - |
testcase_37 | WA | - |
testcase_38 | WA | - |
testcase_39 | WA | - |
testcase_40 | WA | - |
testcase_41 | WA | - |
testcase_42 | WA | - |
testcase_43 | WA | - |
testcase_44 | WA | - |
testcase_45 | WA | - |
testcase_46 | WA | - |
testcase_47 | WA | - |
testcase_48 | WA | - |
testcase_49 | WA | - |
testcase_50 | WA | - |
ソースコード
#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; }