(不得不说,前几年真的水)
枚举最大公约数为d,则数目为n/d,则答案为$\Sigma{d/n}^{d*φ(n/d)}$
`#include[HTML_REMOVED]
include[HTML_REMOVED]
using namespace std;
define int long long
int n,ans,d;
int wljss(int a)
{
int ans=a;
for(int i=2;ii<=a;i)
{
if(a%i==0)
{
ans=ans(i-1)/i;
while(a%i==0)
a/=i;
}
}
if(a>1)
ans=ans(a-1)/a;
return ans;
}
signed main()
{
cin>>n;
for(d=1;d*d<n;d)
{
if(n%d==0)
{
ans+=wljss(n/d)d+wljss(d)(n/d);
}
}
if(dd==n)
ans+=wljss(n/d)*d;
cout<<ans;
}`