結果
問題 | No.2249 GCDistance |
ユーザー |
|
提出日時 | 2023-03-17 22:09:53 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,843 ms / 5,000 ms |
コード長 | 1,906 bytes |
コンパイル時間 | 743 ms |
コンパイル使用メモリ | 74,916 KB |
最終ジャッジ日時 | 2025-02-11 13:17:28 |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 10 |
ソースコード
#include <iostream> #include <cassert> #include <vector> using namespace std; typedef long long ll; struct PrimeStructure { public: PrimeStructure(int max_n) : max_n(max_n), largest_prime_factor(max_n + 1, -1) { for (int i = 2; i <= max_n; i++) { if (largest_prime_factor[i] == -1) { prime_list.push_back(i); for (int j = i; j <= max_n; j += i) { largest_prime_factor[j] = i; } } } } bool is_prime(int n) { assert(n >= 0 && n <= max_n); return largest_prime_factor[n] == n; } std::vector<int> factorize(int n) { assert(n >= 1 && n <= max_n); std::vector<int> res; while (n > 1) { int p = largest_prime_factor[n]; if(res.empty() || p != res.back()) { res.push_back(p); } n /= p; } return res; } int size() { return prime_list.size(); } const int operator[](int i) const { assert(i < (int)prime_list.size()); return prime_list[i]; } std::vector<int>::const_iterator begin() { return prime_list.begin(); } std::vector<int>::const_iterator end() { return prime_list.end(); } private: int max_n; std::vector<int> largest_prime_factor; std::vector<int> prime_list; }; ll s[10000005]; int main() { PrimeStructure prime(10000000); for(int n = 2; n <= 10000000; n++) { int m = n; vector<int> x = prime.factorize(n); for(int p : x) { m = m / p * (p - 1); } s[n] = s[n - 1] + m; } int t; cin >> t; while(t--) { ll n; cin >> n; cout << n * (n - 1) - s[n] << endl; } }