例一

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

#include <bits/stdc++.h>
#define sc(x) scanf("%lld", &(x))
#define pr(x) printf("%lld\n", x)
#define mem(x, y) memset(x, y, sizeof(x))
#define pt putchar(10)
#define For(i, j, k) for (int i = (int)(j); i <= (int)(k); i++)
#define Rep(i, j, k) for (int i = (int)(j); i >= (int)(k); i--)
using namespace std;
typedef long long ll;
const int N = 1e5 + 7;
const ll mod = 1e9 + 7;
const double PI = acos(-1);
const int INF = 0x3f3f3f3f;
int n, mu[N], prime[N], F[N];
bool vis[N];
int cal(int x) {
    int ans = 0;
    while (x) {
        ans += x % 10;
        x /= 10;
    }
    return ans;
}
void init(int n) {
    mu[1] = 1;
    For(i, 2, n) {
        if (!vis[i]) {
            prime[++prime[0]] = i;
            mu[i] = -1;
        }
        for (int j = 1; j <= prime[0] && 1ll * i * prime[j] <= n; j++) {
            vis[i * prime[j]] = 1;
            if (i % prime[j] == 0)
                break;
            mu[i * prime[j]] = -mu[i];
        }
    }
    For(i, 1, n) F[i] = cal(i);
}
int main() {
    cin >> n;
    init(n);
    ll ans = 0;
    For(d, 1, n) {
        if (!mu[d])
            continue;
        ll cur = 0, tmp = n / d;
        For(i, 1, n / d) {
            cur += F[i * d] * tmp;
            tmp--;
        }
        ans += mu[d] * cur;
    }
    cout << ans << endl;
    return 0;
}