【SDOI2012】bzoj2705 Longge的问题

本文主要是介绍【SDOI2012】bzoj2705 Longge的问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

$$\begin{align} & \sum_{i=1}^n \gcd(i,n)\\& =\sum_{i=1}^n \sum_{d\mid\gcd(i,n)} \varphi(d)\\ & = \sum_{i=1}^n \sum_{d\mid i\land d\mid n}\varphi(d)\\& = \sum_{d\mid n} \varphi(d) * \frac dn \end{align}$$

枚举n的因数，再计算欧拉函数求和。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define LL long long
LL phi(LL x)
{int i,m=sqrt(x+0.5);LL ans=x;for (i=2;i<=m;i++)if (x%i==0){ans=ans/i*(i-1);while (x%i==0) x/=i;}if (x>1) ans=ans/x*(x-1);return ans;
}
int main()
{int i,m;LL ans=0,n;scanf("%lld",&n);m=sqrt(n+0.5);for (i=1;i<=m;i++)if (n%i==0&&i<=n/i){ans+=phi(i)*n/i;if (i<n/i) ans+=phi(n/i)*i;}printf("%lld\n",ans);
}

这篇关于【SDOI2012】bzoj2705 Longge的问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---