結果

問題 No.2249 GCDistance
ユーザー V_MelvilleV_Melville
提出日時 2023-03-21 19:13:07
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
CE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,046 bytes
コンパイル時間 4,429 ms
コンパイル使用メモリ 307,044 KB
最終ジャッジ日時 2025-01-25 15:49:35
合計ジャッジ時間 6,521 ms
ジャッジサーバーID
（参考情報） 		judge9 / judge4
このコードへのチャレンジ
（要ログイン）
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。（リジャッジ後のコンパイルエラーは公開されます）
ただし、clay言語の場合は開発者のデバッグのため、公開されます。

コンパイルメッセージ
In file included from /usr/include/c++/13/string:43,
                 from /usr/include/c++/13/bitset:52,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:52,
                 from main.cpp:4:
/usr/include/c++/13/bits/allocator.h: In destructor ‘constexpr std::_Vector_base<long long int, std::allocator<long long int> >::_Vector_impl::~_Vector_impl()’:
/usr/include/c++/13/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘constexpr std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = long long int]’: target specific option mismatch
  184 |       ~allocator() _GLIBCXX_NOTHROW { }
      |       ^
In file included from /usr/include/c++/13/vector:66,
                 from /usr/include/c++/13/functional:64,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:53:
/usr/include/c++/13/bits/stl_vector.h:133:14: note: called from here
  133 |       struct _Vector_impl
      |              ^~~~~~~~~~~~

ソースコード

diff # 

#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target ("avx2")
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;

// totient table
vector<int> ps, pf, phi;
void sieve(int mx) {
    pf.resize(mx+1);
    phi.resize(mx+1);
    phi[1] = 1;
    rep(i, mx+1) pf[i] = i;
    for (int i = 2; i <= mx; ++i) {
        if (pf[i] == i) {
            ps.push_back(i);
            phi[i] = i-1;
        }
        rep(j, ps.size()) {
            int x = ps[j]*i;
            if (x > mx) break;
            pf[x] = ps[j];
            if (i%ps[j] == 0) {
                phi[x] = phi[i]*ps[j];
                break;
            }
            phi[x] = phi[i]*(ps[j]-1);
        }
    }
}

int main() {
    sieve(1e7);
    vector<ll> s(1e7+1);
    rep(i, 1e7) s[i+1] = s[i]+phi[i+1];
    
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        cin >> n;
        ll ans = (ll)n*(n-1) - s[n] + 1;
        cout << ans << '\n';
    }
    
    return 0;
}
0