## 传送门

### 解法：欧拉函数

//1 2 1 2 5 2 1 2 1 10 1 2 1 2 5 2 1 2 1 10 1 2 1 2 25 2 1 2 1 10 1 2 1 2 5 2 1 2 1 10 1 2 1 2 5 2 1 2 1 50

gcd为1的就是与50互质的数，个数为\phi{(N)}

gcd为2的个数怎么算？仔细想想，对于每一个gcd(i,N) = d的数对，都存在gcd(i/d , N/d) = 1

//1 2 1 2 5 2 1 2 1 10 1 2 1 2 5 2 1 2 1 10 1 2 1 2 25 2 1 2 1 10 1 2 1 2 5 2 1 2 1 10 1 2 1 2 5 2 1 2 1 50
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5 + 233, N = 1e5;
int primes[maxn], phi[maxn], cnt;
bool st[maxn];
void get_primes(int n)
{
phi[1] = 1;
for(int i = 2; i <= n; i++)
{
if(!st[i])
{
primes[cnt++] = i;
phi[i] = i - 1;
}
for(int j = 0; j < cnt && i * primes[j] <= n; j++)
{
st[i * primes[j]] = 1;
if(i % primes[j] == 0)
{
phi[i * primes[j]] = phi[i] * primes[j];
break;
}
else phi[i * primes[j]] = phi[i] * (primes[j] - 1);
}
}
}
int euler(int n)
{
int ans = n;
for(int i = 0; i < cnt; i++)
{
if(primes[i] * primes[i] > n) break;
if(n % primes[i] == 0)
{
ans = ans / primes[i] * (primes[i] - 1);
while(n % primes[i] == 0) n /= primes[i];
}
}
if(n > 1) ans = ans / n * (n - 1);
return ans;
}
int main()
{
get_primes(N);
ll n;
ll ans = 0;
cin >> n;
for(int i = 1; (ll)i * i <= n; i++)
{
if(n % i == 0)
{
int t = n / i;
if(t < N) ans += i * phi[t];
else ans += i * euler(t);
if(i != t)
{
ans += t * phi[i];
}
}
}
//if(n > 1) ans += n * euler(n);
cout<<ans;
}