結果
問題 | No.719 Coprime |
ユーザー | Ryuichiro Chiba |
提出日時 | 2021-02-28 15:38:32 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 4,715 bytes |
コンパイル時間 | 928 ms |
コンパイル使用メモリ | 108,004 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-10-02 18:15:11 |
合計ジャッジ時間 | 14,029 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,824 KB |
testcase_02 | AC | 2 ms
6,820 KB |
testcase_03 | AC | 2 ms
6,820 KB |
testcase_04 | AC | 2 ms
6,820 KB |
testcase_05 | WA | - |
testcase_06 | AC | 2 ms
6,820 KB |
testcase_07 | AC | 2 ms
6,816 KB |
testcase_08 | AC | 2 ms
6,824 KB |
testcase_09 | WA | - |
testcase_10 | WA | - |
testcase_11 | WA | - |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | AC | 2 ms
6,820 KB |
testcase_15 | AC | 2 ms
6,816 KB |
testcase_16 | AC | 2 ms
6,816 KB |
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 | AC | 2 ms
6,820 KB |
testcase_27 | AC | 2 ms
6,820 KB |
testcase_28 | AC | 1 ms
6,820 KB |
testcase_29 | WA | - |
testcase_30 | AC | 2 ms
6,820 KB |
testcase_31 | AC | 2 ms
6,820 KB |
testcase_32 | AC | 2 ms
6,816 KB |
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 | - |
testcase_51 | WA | - |
testcase_52 | WA | - |
testcase_53 | WA | - |
testcase_54 | WA | - |
testcase_55 | WA | - |
testcase_56 | WA | - |
testcase_57 | WA | - |
testcase_58 | WA | - |
testcase_59 | WA | - |
testcase_60 | WA | - |
ソースコード
// {{{ #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <climits> #include <iostream> #include <iomanip> #include <algorithm> #include <vector> #include <list> #include <set> #include <unordered_set> #include <map> #include <unordered_map> #include <queue> #include <stack> #include <string> #include <numeric> #include <complex> #include <utility> #include <type_traits> #include <functional> using namespace std; #define fi first #define se second #define pb push_back #define mp make_pair #define FOR(i, a, b) for(ll i = static_cast<ll>(a); i < static_cast<ll>(b); ++i) #define FORR(i, a, b) for(ll i = static_cast<ll>(a); i >= static_cast<ll>(b); --i) #define REP(i, n) FOR(i, 0, n) #define REPR(i, n) FORR(i, n, 0) #define ALL(x) (x).begin(), (x).end() #define DBG(x) cerr << #x << " = " << (x) << " (L" << __LINE__ << ")" << endl; using ll = long long; using ull = unsigned long long; using P = pair<int, int>; using LP = pair<ll, ll>; using IP = pair<int, P>; using LLP = pair<ll, LP>; const int dx[] = {1, -1, 0, 0}; const int dy[] = {0, 0, 1, -1}; constexpr int INF = 100000000; constexpr ll LINF = 10000000000000000ll; constexpr int MOD = static_cast<int>(1e9 + 7); constexpr double EPS = 1e-9; // {{{ popcount static int popcount(int x) { return __builtin_popcount(static_cast<unsigned int>(x)); } static int popcount(unsigned int x) { return __builtin_popcount(x); } static int popcount(long x) { return __builtin_popcountl(static_cast<unsigned long>(x)); } static int popcount(unsigned long x) { return __builtin_popcountl(x); } static int popcount(long long x) { return __builtin_popcountll(static_cast<unsigned long long>(x)); } static int popcount(unsigned long long x) { return __builtin_popcountll(x); } // }}} // template specialization of std::hash for std::pair namespace std { template<typename T, typename U> struct hash<pair<T, U> > { size_t operator()(const pair<T, U> &key) const noexcept { size_t h1 = hash<T>()(key.first); size_t h2 = hash<U>()(key.second); return h1 ^ (h2 << 1); } }; } // namespace std // print vector template<typename T> ostream &operator<<(ostream &os, const vector<T> &v) { size_t sz = v.size(); os << "["; for (size_t i = 0; i < sz-1; i++) { os << v[i] << ", "; } os << v[sz-1] << "]"; return os; } // print array (except char literal) template< typename T, int N, typename std::enable_if<!std::is_same<T, char>::value, std::nullptr_t>::type = nullptr> ostream &operator<<(ostream &os, const T (&v)[N]) { os << "["; for (size_t i = 0; i < N-1; i++) { os << v[i] << ", "; } os << v[N-1] << "]"; return os; } // print array template<typename T> void printArray(T *arr, size_t sz) { cerr << "["; for (size_t i = 0; i < sz-1; i++) { cerr << arr[i] << ","; } if (sz > 0) cerr << arr[sz-1]; cerr << "]" << endl; } // print pair template<typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) { os << "(" << p.first << ", " << p.se << ")"; return os; } static inline ll mod(ll x, ll m) { ll y = x % m; return (y >= 0 ? y : y+m); } struct Compare { //vector<ll> &x_, &y_; //Compare(vector<ll> &x, vector<ll> &y): x_(x), y_(y) {} //bool operator()(const P &lhs, const P &rhs) { // return x_[lhs.fi]+y_[lhs.se] < x_[rhs.fi]+y_[rhs.se]; //} bool operator()(const int x, const int y) { return x < y; } }; // print floating-point number // cout << fixed << setprecision(12) << // }}} int N; bool prime[100000]; vector<int> p; void sieve(ll n) { REP (i, n+1) prime[i] = true; prime[0] = prime[1] = false; FOR (i, 2, n+1) { if (prime[i]) { p.pb(i); for (ll j = 2*i; j <= n; j += i) { prime[j] = false; } } } } bool isCoprime(int x, int y) { bool ret = true; for (int i: p) { if (i > min(x, y)) break; if (x % i == 0 && y % i == 0) { return false; } } return true; } void solve() { sieve(N); int ret = 0; FORR (x, N, 2) { vector<int> s; FORR (i, x, 2) { bool ok = true; for (int v: s) { if (!isCoprime(i, v)) { ok = false; break; } } if (ok) s.pb(i); } int t = 0; for (int v: s) t += v; ret = max(ret, t); } cout << ret << endl; } int main() { cin.tie(0); ios::sync_with_stdio(false); cin >> N; solve(); return 0; } // vim:set foldmethod=marker: