結果
問題 | No.2249 GCDistance |
ユーザー | kumakuma |
提出日時 | 2023-03-13 05:57:06 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,333 ms / 5,000 ms |
コード長 | 1,427 bytes |
コンパイル時間 | 2,363 ms |
コンパイル使用メモリ | 205,028 KB |
実行使用メモリ | 160,696 KB |
最終ジャッジ日時 | 2023-10-18 10:54:14 |
合計ジャッジ時間 | 21,411 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1,247 ms
160,696 KB |
testcase_01 | AC | 1,288 ms
160,696 KB |
testcase_02 | AC | 1,290 ms
160,696 KB |
testcase_03 | AC | 1,298 ms
160,696 KB |
testcase_04 | AC | 1,264 ms
160,696 KB |
testcase_05 | AC | 1,333 ms
160,696 KB |
testcase_06 | AC | 1,314 ms
160,696 KB |
testcase_07 | AC | 1,301 ms
160,696 KB |
testcase_08 | AC | 1,237 ms
160,696 KB |
testcase_09 | AC | 1,294 ms
160,696 KB |
testcase_10 | AC | 1,300 ms
160,696 KB |
ソースコード
#include <bits/stdc++.h> // #include <atcoder/modint> #define rng(a) a.begin(),a.end() #define rrng(a) a.rbegin(),a.rend() #define INF 2000000000000000000 #define ll long long #define ull unsigned long long #define ld long double #define pll pair<ll, ll> using namespace std; template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; } template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; } const double PI = 3.141592653589793; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll T; cin >> T; ll before = 0; ll M = 10000010; vector<ll> dp(M); vector<bool> already(M, false); for (ll i = 0; i < M; ++i) { dp.at(i) = i; } for (ll i = 2; i < M; ++i) { if (already.at(i)) { continue; } ll cnt = 1; while (cnt * i < M) { dp.at(cnt * i) /= i; dp.at(cnt * i) *= i - 1; already.at(cnt * i) = true; cnt += 1; } } vector<ll> dp2(M, 0); for (ll i = 2; i < M; ++i) { dp2.at(i) = (i - 1) * 2 - (dp.at(i)); } for (ll i = 0; i < M - 1; ++i) { dp2.at(i + 1) += dp2.at(i); } // for (ll i = 0; i < 10; ++i) { // cout << dp.at(i) << " "; // } // cout << "\n"; // for (ll i = 0; i < 10; ++i) { // cout << dp2.at(i) << " "; // } // cout << "\n"; for (ll testcase = 0; testcase < T; ++testcase) { ll N; cin >> N; cout << dp2.at(N) << "\n"; } }