結果

問題 No.2249 GCDistance
ユーザー kcvlex
提出日時 2023-03-17 22:43:26
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 1,336 bytes
コンパイル時間 3,608 ms
コンパイル使用メモリ 153,744 KB
最終ジャッジ日時 2025-02-11 13:48:03
ジャッジサーバーID
（参考情報） 		judge2 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample MLE * 1
other MLE * 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