[SDOI 2012]Longge的问题

Description

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

Input

一个整数，为N。

Output

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

Sample Input

Sample Output

HINT

【数据范围】
对于60%的数据，0<N<=2^16。
对于100%的数据，0<N<=2^32。

题解

求 $$\sum_{i = 1}^N gcd(i, N)$$

用惯用的套路我们枚举 $N$ 的因子 $$\sum_{d \mid N} d \cdot \sum_{i = 1}^{ \frac{N}{d} } \left[gcd \left( \frac{N}{d} , i \right) = 1\right]$$

化简为 $$\sum_{d \mid N} d \cdot \varphi \left( \frac{N}{d} \right)$$

欧拉函数直接用 $\varphi(n) = n \cdot \prod_{i = 1}^k \left(1-\frac{1}{p_i} \right)$ 来求。

 //It is made by Awson on 2018.1.12

 #include <set>

 #include <map>

 #include <cmath>

 #include <ctime>

 #include <queue>

 #include <stack>

 #include <cstdio>

 #include <string>

 #include <vector>

 #include <cstdlib>

 #include <cstring>

 #include <iostream>

 #include <algorithm>

 #define LL long long

 #define Max(a, b) ((a) > (b) ? (a) : (b))

 #define Min(a, b) ((a) < (b) ? (a) : (b))

 #define Swap(a, b) ((a) ^= (b), (b) ^= (a), (a) ^= (b))

 using namespace std;

 void read(LL &x) {

     char ch; bool flag = ;

     for (ch = getchar(); !isdigit(ch) && ((flag |= (ch == '-')) || ); ch = getchar());

     for (x = ; isdigit(ch); x = (x<<)+(x<<)+ch-, ch = getchar());

     x *= -*flag;

 }

 void write(LL x) {

     if (x > ) write(x/);

     putchar(x%+);

 }

 LL n, m, ans;

 LL phi(LL x) {

     LL ans = x;

     for (LL i = ; i <= m; i++) {

     if (x%i) continue;

     ans = ans*(i-)/i;

     while (!(x%i)) x /= i;

     }

     if (x > ) ans = ans*(x-)/x;

     return ans;

 }

 void work() {

     read(n); m = sqrt(n);

     for (LL i = ; i <= m; i++) {

     if (n%i) continue;

     ans += i*phi(n/i);

     if (i*i < n) ans += n/i*phi(i);

     }

     write(ans);

 }

 int main() {

     work();

     return ;

 }

巴特西