出题人怎么这么不认真啊==明明官方译名是爱蜜莉雅……
而且我们爱蜜莉雅碳是有英文名哒！是Emilia。你那个aimiliya我实在是无力吐槽……
不过抱图跑23333首先这很像约数个数和函数诶！
但是唯一的不同是，D(1)=1,F(1)=0.
那么如果就是D，我们怎么做？
原题意思是求以下式子：
$Anssumlimits_{i=1}^{n}d(gcd(i,n))$
我们知道：
$D(n)=sumlimits_{d|n}1$
所以：
$Ans=sumlimits_{d|n}sumlimits_{i=1}^{frac{n}{d}}D(d)[gcd(i,frac{n}{d}==1]$
$Ans=sumlimits_{d|n}D(d)*sumlimits_{i=1}^{frac{n}{d}}[gcd(i,frac{n}{d}==1]$
第二个求和就相当于枚举跟$frac{n}{d}$互质的数。这不是$phi$的定义吗？
所以：
$Ans=sumlimits_{d|n}D(d)*phi(frac{n}{d})$
这是……狄利克雷卷积？
$D*phi=1*1*phi=id*1$
$Ans=sumlimits_{d|n}frac{n}{d}$
那么如果是这个呢？这个f(1)=0的话，我们相当于把1多算了$phi(n)$次，减去就行了。
所以最后：
$Ans=sumlimits_{d|n}frac{n}{d}-phi(n)$
复杂度：$O(sqrt{n})$
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 ll n; 5 ll calcsum(ll n){ 6 int m=(int)sqrt(n+0.5); 7 ll cnt=0,ans=0; 8 for(int i=1;i<=m;i++){ 9 if(n%i==0){ 10 ans+=i;if(i*i!=n)ans+=n/i; 11 else break; 12 } 13 } 14 return ans; 15 } 16 ll calcphi(ll n){ 17 int m=(int)sqrt(n+0.5); 18 ll ans=n; 19 for(int i=2;i<=m;i++)if(n%i==0){ 20 ans=ans/i*(i-1); 21 while(n%i==0)n/=i; 22 if(n==1)break; 23 } 24 if(n>1)ans=ans/n*(n-1); 25 return ans; 26 } 27 int main(){ 28 freopen("aimiliyadehelp.in","r",stdin); 29 freopen("aimiliyadehelp.out","w",stdout); 30 cin>>n; 31 cout<<calcsum(n)-calcphi(n)<<endl; 32 return 0; 33 }