結果

問題 No.2249 GCDistance
ユーザー kcvlexkcvlex
提出日時 2023-03-17 22:43:26
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
MLE  
実行時間 -
コード長 1,336 bytes
コンパイル時間 3,215 ms
コンパイル使用メモリ 163,368 KB
実行使用メモリ 550,564 KB
最終ジャッジ日時 2023-10-18 15:43:47
合計ジャッジ時間 16,397 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
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;
    
std::vector<std::vector<int>> p_divs(SIZE);

int calc_non_disj(int num, int idx, int acc) {
    if (idx == p_divs[num].size()) return (acc == 1 ? 0 : (num - 1) / acc);
    return calc_non_disj(num, idx + 1, acc) - calc_non_disj(num, idx + 1, acc * p_divs[num][idx]);
}

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;
        }
    }

    for (auto p : primes) {
        for (int i = p; i < SIZE; i += p) {
            p_divs[i].push_back(p);
        }
    }

    std::vector<int> non_disj(SIZE);
    for (int i = 1; i < SIZE; i++) {
        non_disj[i] = -calc_non_disj(i, 0, 1);
    }

    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