結果
問題 | No.2249 GCDistance |
ユーザー |
|
提出日時 | 2023-03-18 01:22:03 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,407 ms / 5,000 ms |
コード長 | 843 bytes |
コンパイル時間 | 3,212 ms |
コンパイル使用メモリ | 75,512 KB |
最終ジャッジ日時 | 2025-02-11 14:44:26 |
ジャッジサーバーID (参考情報) |
judge1 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 10 |
ソースコード
#include <stdio.h>#include <iostream>#include <vector>#include <queue>#include <stack>#include <algorithm>#pragma GCC optimize("O2")using ll = long long int;const int INF = (1<<30);const ll INFLL = (1ll<<60);const ll MOD = (ll)(1e9+7);#define l_ength sizevoid mul_mod(ll& a, ll b){a *= b;a %= MOD;}void add_mod(ll& a, ll b){a = (a<MOD)?a:(a-MOD);b = (b<MOD)?b:(b-MOD);a += b;a = (a<MOD)?a:(a-MOD);}bool f[10010010];ll memo[10010010],ans[10010010];int main(void){int t;ll i,j,n=10000000;for(i=2; i<=n; ++i){memo[i] = i;}for(i=2; i<=n; ++i){if(!f[i]){for(j=i; j<=n; j+=i){memo[j] /= i;memo[j] *= (i-1);f[j] = true;}}ans[i] = ans[i-1] + (i-memo[i]-1)*2+memo[i];}std::cin >> t;while(t--){std::cin >> n;std::cout << ans[n] << std::endl;}return 0;}