結果
問題 | No.2249 GCDistance |
ユーザー |
![]() |
提出日時 | 2023-03-17 21:56:07 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 671 ms / 5,000 ms |
コード長 | 801 bytes |
コンパイル時間 | 1,667 ms |
コンパイル使用メモリ | 196,264 KB |
最終ジャッジ日時 | 2025-02-11 13:01:47 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 10 |
ソースコード
#include<bits/stdc++.h> using namespace std; using int64 = long long; #line 1 "math/number-theory/euler-phi-table.hpp" /** * @brief Euler’s Phi Table(オイラーのφ関数テーブル) * @docs docs/euler-phi-table.md */ vector< int > euler_phi_table(int n) { vector< int > euler(n + 1); for(int i = 0; i <= n; i++) { euler[i] = i; } for(int i = 2; i <= n; i++) { if(euler[i] == i) { for(int j = i; j <= n; j += i) { euler[j] = euler[j] / i * (i - 1); } } } return euler; } int main() { auto X = euler_phi_table(1e7); vector< int64 > sum(1e7+1); for(int i = 1; i < sum.size(); i++) { if(i>0)sum[i]+=sum[i-1]; sum[i]+=X[i]; } int T; cin >> T; while(T--) { int N; cin >> N; cout << 1ll*N*(N-1)-sum[N]+1<<endl; } }