#P2303. [SDOI2012] Longge 的问题

    ID: 1314 远端评测题 3000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>数论数学2012各省省选山东O2优化

[SDOI2012] Longge 的问题

题目背景

Longge 的数学成绩非常好,并且他非常乐于挑战高难度的数学问题。

题目描述

现在问题来了:给定一个整数 nn,你需要求出 i=1ngcd(i,n)\sum\limits_{i=1}^n \gcd(i, n),其中 gcd(i,n)\gcd(i, n) 表示 iinn 的最大公因数。

输入格式

输入只有一行一个整数,表示 nn

输出格式

输出一行一个整数表示答案。

6
15

提示

数据规模与约定

  • 对于 60%60\% 的数据,保证 n216n\leq 2^{16}
  • 对于 100%100\% 的数据,保证 1n<2321\leq n< 2^{32}