\(\Large f(n)=\sum_{i=1}^{n}gcd(i,n)\)
设 \(g(n)=gcd(i,n)\) \((1\leq i\leq n)\)
设 \(n=ab\) ，且\(gcd(a,b)=1\)，则有 \(g(n)=g(a)g(b)\)，所以 \(g\) 是积性函数；
又，由于积性函数的和也是积性函数，所以 \(f(n)=\sum_{i=1}^{n}gcd(i,n)\) 也是积性函数。
设 \(n\) 的唯一分解式是 :
\[n=p_1^{a_1}p_2^{a_2}...p_n^{a_n}
\]
\]
则:
\[f(n)=f(p_1^{a_1}p_2^{a_2}...p_k^{a_k})=\prod_{i=1}^k f(p_i^{a_i})
\]
\]
对于 \(\phi(n)\)有：
\[\begin{align*}
\phi(n)=\prod_{i=1}^k(p_i^{a_i}-p_i^{a_i-1})
\color{#ddd}{=m\prod_{i=1}^k1-\frac1{p_i}}
\end{align*}
\]
\phi(n)=\prod_{i=1}^k(p_i^{a_i}-p_i^{a_i-1})
\color{#ddd}{=m\prod_{i=1}^k1-\frac1{p_i}}
\end{align*}
\]
对于 \(f(p^{a})\) 有：
\[\begin{align*}
f(p^a)&=\phi(p^a)+p\phi(p^{a-1})+...+p^a\phi(1)\\
&=(p^a-p^{a-1})+p(p^{a-1}-p^{a-2})+...+p^{a-1}(p-p^0)+p^a\\
&=a(p^a-p^{a-1})+p^a
\end{align*}
\]
f(p^a)&=\phi(p^a)+p\phi(p^{a-1})+...+p^a\phi(1)\\
&=(p^a-p^{a-1})+p(p^{a-1}-p^{a-2})+...+p^{a-1}(p-p^0)+p^a\\
&=a(p^a-p^{a-1})+p^a
\end{align*}
\]
所以：
\[\begin{align*}
f(n)&=f(p_1^{a_1}p_2^{a_2}...p_k^{a_k})\\
&=\prod_{i=1}^k f(p_i^{a_i})\\
&=\prod_{i=1}^ka_i(p_i^{a_i}-p_i^{a_i-1})+p_i^{a_i}
\end{align*}
\]
f(n)&=f(p_1^{a_1}p_2^{a_2}...p_k^{a_k})\\
&=\prod_{i=1}^k f(p_i^{a_i})\\
&=\prod_{i=1}^ka_i(p_i^{a_i}-p_i^{a_i-1})+p_i^{a_i}
\end{align*}
\]
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e6+5;
inline ll kpow(ll a,ll b)
{
ll ans=1;
while(b)
{
if(b&1)ans*=a;
a*=a;
b>>=1;
}
return ans;
}
int pri[maxn+5];
void init()
{
for(int i=2;i<maxn;i++)
{
if(!pri[i])pri[++pri[0]]=i;
for(int j=1;j<=pri[0]&&i*pri[j]<maxn;j++)
{
pri[i*pri[j]]=1;
if(i%pri[j]==0)break;
}
}
}
int fac[maxn],num[maxn];
inline ll cal(ll p,ll a){return kpow(p,a)+kpow(p,a-1)*a*(p-1);}
int main()
{
init();
int n;ll ans=1;
scanf("%d",&n);
for(int i=1;pri[i]*pri[i]<=n;i++)
{
if(n%pri[i]==0)
{
fac[++fac[0]]=pri[i];
while(n%pri[i]==0)n/=pri[i],num[fac[0]]++;
}
}
if(n>1)fac[++fac[0]]=n,num[fac[0]]=1;
for(int i=1;i<=fac[0];i++)
ans*=cal(fac[i],num[i]);
printf("%lld\n",ans);
}
原文链接: https://www.cnblogs.com/kkkek/p/12554862.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/337218
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
