题目链接：bzoj2705 题目大意： 求 ∑ni=1gcd(i,n) \sum_{i=1}^{n}gcd(i,n)， 0<N≤232 0<N≤2^{32}。 题解： 数论，欧拉函数 设 d d为nn的约数，有 i=i′×d i=i'\times d 于是式子就可以写成 ∑d|nd∑1≤i′d≤n,(i′d,n)=d1 \sum_{d|n}d\sum_{1≤i'd≤n,(i'

题意: Given an integer N(1 < N < 2^31),you are to calculate ∑gcd(i, N) 1<=i <=N. 题解： 公式：f(N)=∑x*φ(N/x)，x | N （x是N的约数） 因为在1···N中，gcd(i，N) = x， 的个数的等于φ(N / x) 另外还可以利用函数的积性： 对于正整数n的一个函数 f(n)，当中f(1)=1且

Description Longge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数N，你需要求出∑gcd(i, N)(1<=i <=N)。 Input 一个整数，为N。 Output 一个整数，为所求的答案。 ∑i=1ngcd(i,n)=∑i=1n∑d∣gcd(i,n)φ(d)=∑i=1n∑d∣i∧d∣nφ(d)=∑d∣nφ(d)∗dn \

Description Longge的数学成绩非常好，并且他非常乐于挑战高难度的数学问题。现在问题来了：给定一个整数N，你需要求出∑gcd(i, N)(1<=i <=N)。 Input 一个整数，为N。 Output 一个整数，为所求的答案。 Sample Input 6 Sample Output 15 HINT 【数据范围】 对于60%的数据，0< N<=2^16。