A Simple Math Problem

题目大意

输入描述

输出描述

样例

输入

3

输出

5

推导

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e6+1;

int prime[maxn], mu[maxn], phi[maxn], tot;
bool vis[maxn];
int f[maxn];

void get_pmp(int n) {
    vis[1] = mu[1] = phi[1] = 1;
    for(int i = 2; i <= n; ++ i) {
        if (!vis[i]) {
            prime[++tot] = i;
            mu[i] = -1;
            phi[i] = i-1;
        }
        for(int j = 1; prime[j] <= n/i; ++ j) {
            vis[prime[j]*i] = 1;
            phi[prime[j]*i] = prime[j] * phi[i];
            if (i % prime[j] == 0) break;
            mu[prime[j]*i] = mu[prime[j]] * mu[i];
            phi[prime[j]*i] = phi[prime[j]] * phi[i];
        }
    }
}

void get_f(int n) {
    for(int i = 1; i <= n; ++ i) {
        int t = i;
        while(t) {
            f[i] += t%10;
            t /= 10;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    get_pmp(n);
    get_f(n);
    long long res = 1;
    for(int i = 1; i <= n; ++ i) {
        long long t = 0;
        for(int j = 1; j <= n/i; ++ j) {
            t += f[j*i];
        }
        res += mu[i] * n/i * t - phi[i] * f[i];
    }
    cout << res << "\n";
    return 0;
}

代码