BZOJ2705 - [SDOI2012]Longge的问题

BZOJ2705 - Click Here

  

Description

  Longge的数学成绩非常好,并且他非常乐于挑战高难度的数学问题。现在问题来了:给定一个整数N,你需要求出∑gcd(i, N)(1<=i <=N)。

  

Input

  一个整数,为N。

  

Output

  一个整数,为所求的答案。

  

Solutions

  $N$是固定的,因此$(i,N)$只可能是$N$的约数,而$N$的约数最多只有$2\sqrt N$个。

  

  考虑枚举约数,则答案变成$\sum_{k \mid N} k\sum_{1 \leq i \leq N} [(i,N)=k]$

  对内层和式变形可得,$\sum_{k \mid N} k\sum_{1 \leq i \leq N}[(\frac{i}{k},\frac{N}{k})=1]$

  内层和式$\sum_{1 \leq i \leq N}[(\frac{i}{k},\frac{N}{k})=1]$实质上就是$\phi(\frac{N}{k})$

  因此最后答案为$\sum_{k \mid N}k \cdot \phi(\frac{N}{k})$

  

  暴力求欧拉函数即可。

  时间复杂度$O(N)$。不过这个上界很宽松,实际在OJ上是能跑过的qwq。

  

CODE

CODE - Click Here

本站总访问量次 | 本站访客数人次

Powered by Hexo | Designed by iTimeTraveler | Refined by CSHwang