2020江西ICPC省赛 A.Simple Math Problem(莫比乌斯反演)

题目链接

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
ll F[N];
int mu[N];
int Log(int n){
    int ans=0;
    while(n)ans+=n%10,n/=10;
    return ans;
}
void pre(){
    mu[1]=1;
    for(int i=1;i<N;i++){
        F[i]=Log(i);
        if (mu[i]){
            for(int j=2*i;j<N;j+=i){
                mu[j]-=mu[i];
            }
        }
    }
}
int main(){
    pre();
    int n;scanf("%d",&n);
    ll ans=0;
    for(int d=1;d<=n;d++){
        if(mu[d]){
            ll m=n/d,s=0;
            for(int i=d;i<=n;i+=d){
                s+=1LL*F[i]*m;
                m--;
            }
            ans+=s*mu[d];
        }
    }
    printf("%lld\n",ans);
}