#P1875. 「Longge's problem」 龙哥的问题

「Longge's problem」 龙哥的问题

龙哥现在有一道题,要考考大家。

给定一个整数N,请你求出_1iNgcdiN)\sum\_{1 \le i \le N} gcd(i,N)的值。

输入格式

一个整数N。

输出格式

一个整数表示结果。

数据范围

1<N<2311 < N < 2^{31}

输入样例:

6

输出样例:

15

来源

  • 《算法竞赛进阶指南》
  • acwing 可能含有视频讲解