题目：https://www.lydsy.com/JudgeOnline/problem.php?id=2705
一开始自己想了半天...
有了点思路：遍历 n 的因数 k，每个因数要预处理出 gcd 等于这个因数的数的个数 s[k]；
预处理过程中还要去重：s[k] = (n-1) / k , s[k] -= s[2*k] + s[3*k] +......，&(*%$^&...
正要勇猛去写的时候还是点开了TJ，然后被自己的愚蠢暴击...
考虑 gcd ( n , m ) = k 的 m 的个数，发现 gcd ( n/k , m/k ) = 1，也就是 phi ( n/k )！！！
所以遍历因数，求它们的欧拉函数；
但范围太大了不能预处理，所以暴力每次求；
然而发现自己暴力也不会了，想了许多纯纯的暴力...
还是要用公式的啊... phi (x) = x * ∏ ( 1 - 1 / p[i] )；
总之，就是一道关于欧拉函数的水题...
代码如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long ll;
ll n,ans;
ll phi(ll x)
{
ll ret=x;
for(int i=;i*i<=x;i++)
if(x%i==)
{
ret=ret/i*(i-);//防止溢出
while(x%i==)x/=i;
}
if(x>) ret=ret/x*(x-);
return ret;
}
int main()
{
scanf("%lld",&n);
for(int i=;i*i<=n;i++)
if(n%i==)
{
ans+=i*phi(n/i);
if(i*i<n) ans+=n/i*phi(i);//别算2遍 sqrt(n)
}
printf("%lld",ans);
return ;
}