結果

問題 No.2249 GCDistance
ユーザー kcvlexkcvlex
提出日時 2023-03-17 22:37:52
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
MLE  
実行時間 -
コード長 1,521 bytes
コンパイル時間 3,232 ms
コンパイル使用メモリ 164,392 KB
実行使用メモリ 814,620 KB
最終ジャッジ日時 2024-09-18 11:43:37
合計ジャッジ時間 11,450 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 MLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <atcoder/all>

#define ALL(V) std::begin(V), std::end(V)

const int SIZE = 1e7 + 10;

using ll = long long;

int main() {
    std::vector<int> primes;
    {
        std::vector<bool> flags(SIZE);
        for (int i = 2; i < SIZE; i++) {
            if (flags[i]) continue;
            primes.push_back(i);
            for (int j = i; j < SIZE; j += i) flags[j] = true;
        }
    }

    std::vector<std::vector<std::pair<int, int>>> p_divs(SIZE);
    for (auto &v : p_divs) v.emplace_back(1, 0);
    for (auto p : primes) {
        for (int i = p; i < SIZE; i += p) {
            int sz = p_divs[i].size();
            for (int j = 0; j < sz; j++) {
                auto [ a, b ] = p_divs[i][j];
                p_divs[i].emplace_back(a * p, b + 1);
            }
        }
    }

    std::vector<int> non_disj(SIZE);
    for (int i = 1; i < SIZE; i++) {
        int tmp = 0;
        for (auto [ d, cnt ] : p_divs[i]) {
            if (d == 1 || d == i) continue;
            if (cnt % 2 == 1) tmp += (i - 1) / d;
            else tmp -= (i - 1) / d;
        }
        non_disj[i] = tmp;
    }

    std::vector<ll> sum(SIZE + 1);
    for (int i = 0; i < SIZE; i++) sum[i + 1] = sum[i] + non_disj[i];

    std::ios::sync_with_stdio(false);
    int T;
    std::cin >> T;
    while (T--) {
        ll N;
        std::cin >> N;
        ll ans = N * (N - 1) / 2;
        ans += sum[N + 1];
        std::cout << ans << '\n';
    }
    return 0;
}
0