bzoj2705[SDOI2012] Longge的问题

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

题目链接：bzoj2705
题目大意：
求$\sum_{i=1}^{n}gcd(i,n)$，$0<N≤2^{32}$。

题解：
数论，欧拉函数
设$d$为$n$的约数，有$i=i'\times d$
于是式子就可以写成

$$\sum_{d|n}d\sum_{1≤i'd≤n,(i'd,n)=d}1$$
即 $$\sum_{d|n}d\sum_{1≤i'≤\dfrac{n}{d},(i',\dfrac{n}{d})=1}1$$
继而化为： $$\sum_{d|n}d\times \phi(\dfrac{n}{d})$$
于是就 $O(\sqrt{n})$枚举 $d$，直接计算$\phi(\dfrac{n}{d})$，累加就好了。
额，先 $O(\sqrt{n})$预处理出 $n$的所有质因子吧，因为$\dfrac{n}{d}$的质因子一定也在 n <script type="math/tex" id="MathJax-Element-60">n</script>的质因子中。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;LL cnt,pri[50];
void get_pri(LL x,LL lim)
{cnt=0;for (LL i=2;x!=1 && i<=lim;i++) if (x%i==0){pri[++cnt]=i;while (x%i==0) x/=i;}if (x!=1) pri[++cnt]=x;
}
LL phi(LL x)
{LL ret=x;for (LL i=1;i<=cnt;i++)if (x%pri[i]==0) ret=ret*(pri[i]-1)/pri[i];return ret;
}
int main()
{//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);LL i,n,ans=0;scanf("%lld",&n);LL m=(LL)sqrt(n);get_pri(n,m);for (i=1;i<=m;i++) if (n%i==0){LL x=i,y=n/i;ans+=x*phi(y);ans+=y*phi(x);}if (m*m==n) ans-=m*phi(m);printf("%lld\n",ans);return 0;
}

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

---