問題一覧 > 通常問題

No.2249 GCDistance

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 109
作問者 : bayashikobayashiko / テスター : kumakumakumakuma AngrySadEightAngrySadEight
3 ProblemId : 9320 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-03-13 14:32:41

問題文

$N$ 頂点の重み付き無向完全グラフ $G$ があり、 $G$ の各頂点には $1$ から $N$ の番号が付けられています。

$G$ の頂点 $i$ と頂点 $j(i < j)$ を結ぶ辺の重みは $\gcd(i,j)$ 、つまり $i$ と $j$ の最大公約数です。

$dist(x,y)$ を、頂点 $x$ からいくつかの辺を辿って頂点 $y$ へ移動するときに辿る辺の重みの総和の最小値とします。

$\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} dist(i,j)$ を求めてください。なお、制約の条件下で答えは $2^{63}$ 未満であることが保証されます。

$1$ つの入力ファイルにつき $T$ 個のテストケースに答えてください。

入力

$T$
$case_1$
$case_2$
:
$case_T$
各テストケースは以下の形式で与えられます。
$N$

  • $1\le T \le 2×10^5$
  • $2\le N\le 10^7$
  • 入力はすべて整数

出力

答えを出力してください。 $i$ 行目には $i$ 個目のテストケースに対する答えを出力してください。

サンプル

サンプル1
入力
3
2
4
10000000
出力
1
7
69603633572759

$N=2$ のとき、 $dist(1,2)=1$ なので、 $1$ 個目のテストケースに対する答えは $1$ です。

$N=4$ のとき、 $dist(1,2)=1,dist(1,3)=1,dist(1,4)=1,dist(2,3)=1,dist(2,4)=2,dist(3,4)=1$ なので、 $2$ 個目のテストケースに対する答えは $1+1+1+1+2+1=7$ です。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。