結果
問題 |
No.2249 GCDistance
|
ユーザー |
![]() |
提出日時 | 2023-03-17 22:37:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 840 bytes |
コンパイル時間 | 1,781 ms |
コンパイル使用メモリ | 198,892 KB |
最終ジャッジ日時 | 2025-02-11 13:42:03 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | TLE * 10 |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long int ll; map<ll,ll> memo; ll sum_of_totient(ll N){ if (memo.find(N)!=memo.end()){ return memo[N]; } if (N==1){ return 1; } else if(N==2){ return 2; } ll tmp=N-1; ll ans=((N*(N+1)))/2; ll k=1; while(N/k>N/(k+1)){ tmp-=(N/k)-(N/(k+1)); ans-=((N/k)-(N/(k+1)))*sum_of_totient(k); k++; } ll i=2; while(tmp>0){ tmp--; ans-=sum_of_totient(N/i); i++; } memo[N]=ans; return ans; } ll solve(ll N){ ll res=sum_of_totient(N)*2-1; ll ans=(2*N*N-res); ans-=2*N-1; ans/=2; return ans; } int main(void){ int T; cin>>T; for (int i=0;i<T;i++){ ll N; cin>>N; cout<<solve(N)<<endl; } return 0; }