bjut193E 吃饭时的怪癖

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 
 4 int euler(int n)
 5 {
 6     int res = n;
 7     for (int i = 2; i * i <= n; i++)
 8     {
 9         if (n % i == 0)
10         {
11             res = res / i * (i - 1);
12             while (n % i == 0) n /= i;
13         }
14     }
15     if (n > 1) res = res / n * (n - 1);
16     return res;
17 }  
18 
19 int main()
20 {
21     int n;
22     while (cin >> n)
23     {
24         cout << (n == 1 ? 1 : (long long)euler(n) * n / 2) << endl;
25     }
26     return 0;
27 }