結果
問題 | No.2249 GCDistance |
ユーザー |
|
提出日時 | 2023-03-18 05:52:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,116 ms / 5,000 ms |
コード長 | 1,010 bytes |
コンパイル時間 | 1,701 ms |
コンパイル使用メモリ | 196,088 KB |
最終ジャッジ日時 | 2025-02-11 14:56:36 |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 10 |
ソースコード
/*** - Meet Brahmbhatt* - Hard work always pays off**/#include"bits/stdc++.h"using namespace std;#ifdef MeetBrahmbhatt#include "debug.h"#else#define dbg(...) 72#endif#define endl "\n"#define int long long#define sz(x) (int)(x.size())const long long INF = 4e18;const int32_t M = 1e9 + 7;const int32_t MM = 998244353;const int32_t N = 1e7 + 5;vector<int> phi(N);vector<bool> P(N, 1);vector<int> dp(N);void pre() {iota(phi.begin(), phi.end(), 0);for (int i = 2; i < N; i++) {if (P[i]) {phi[i]--;for (int j = 2 * i; j < N; j += i) {P[j] = 0;phi[j] /= i;phi[j] *= (i - 1);}}}dp[2] = 1;for (int i = 3; i < N; i++) {dp[i] = dp[i - 1] + (i - 1 - phi[i]) * 2 + phi[i];}}void solve() {int n;cin >> n;cout << dp[n] << endl;}signed main() {ios_base::sync_with_stdio(0);cin.tie(0);cout << fixed << setprecision(9);int tt = 1;pre();cin >> tt;while (tt--) solve();return 0;}