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

A Simple Math Problem

https://ac.nowcoder.com/acm/contest/8827/A

题目链接

$Description$

在这里插入图片描述

$Solution$

$\sum_{i=1}^{n}\sum_{j=1}^{i}F(j)[gcd(i,j)=1]$
$=\sum_{i=1}^{n}\sum_{j=1}^{i}F(j)\sum_{d|gcd(i,j)}\mu(d)$
$=\sum_{i=1}^{n}\sum_{d|i}\mu(d)\sum_{j=1}^{i}F(j)[d|j]$
$=\sum_{i=1}^{n}\sum_{d|i}\mu(d)\sum_{j=1}^{\frac{i}{d}}F(j\cdot d)$
$=\sum_{d=1}^{n}\mu(d)\sum_{i=1}^{\frac{n}{d}}F(i\cdot d)\cdot (\frac{n}{d}-i+1)$

$Code$

#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);
}