結果
問題 | No.2249 GCDistance |
ユーザー |
![]() |
提出日時 | 2023-03-17 21:36:50 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 2,456 ms / 5,000 ms |
コード長 | 905 bytes |
コンパイル時間 | 1,501 ms |
コンパイル使用メモリ | 171,248 KB |
実行使用メモリ | 121,728 KB |
最終ジャッジ日時 | 2024-09-18 10:25:07 |
合計ジャッジ時間 | 29,624 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 10 |
ソースコード
#include <bits/stdc++.h>using namespace std;const int MAX = 10000000;int main(){vector<bool> prime(MAX + 1, true);vector<int> mobius(MAX + 1, 1);for (int i = 2; i <= MAX; i++){if (prime[i]){mobius[i] *= -1;for (int j = i * 2; j <= MAX; j += i){mobius[j] *= -1;prime[j] = false;}}}for (int i = 2; i * i <= MAX; i++){for (int j = i * i; j <= MAX; j += i * i){mobius[j] = false;}}vector<long long> C(MAX + 1, 0);for (int i = 2; i <= MAX; i++){for (int j = i; j <= MAX; j += i){C[j] -= (j / i - 1) * mobius[i];}}for (int i = 2; i <= MAX; i++){C[i] += C[i - 1];}int T;cin >> T;for (int i = 0; i < T; i++){int N;cin >> N;long long all = (long long) N * (N - 1) / 2;long long two = C[N];long long one = all - two;cout << one + two * 2 << endl;}}