题面

Sol

傻逼题

# include 
    
     # define RG register# define IL inline# define Fill(a, b) memset(a, b, sizeof(a))using namespace std;typedef long long ll;const int _(1e7 + 1);IL ll Read(){    char c = '%'; ll x = 0, z = 1;    for(; c > '9' || c < '0'; c = getchar()) if(c == '-') z = -1;    for(; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0';    return x * z;}int prime[_], mu[_], num, s[_];bool isprime[_];IL void Prepare(){    isprime[1] = 1; mu[1] = 1;    for(RG int i = 2; i < _; ++i){        if(!isprime[i]) prime[++num] = i, mu[i] = -1;        for(RG int j = 1; j <= num && i * prime[j] < _; ++j){            isprime[i * prime[j]] = 1;            if(i % prime[j])  mu[i * prime[j]] = -mu[i];            else{  mu[i * prime[j]] = 0; break;  }        }        mu[i] += mu[i - 1]; s[i] = s[i - 1] + (!isprime[i]);    }}IL ll Calc(RG ll n){    RG ll f = 0;    for(RG ll i = 1, j; i <= n; i = j + 1) j = n / (n / i), f += 1LL * (mu[j] - mu[i - 1]) * (n / i) * (n / i);    return f;}int main(RG int argc, RG char *argv[]){    Prepare();    RG int n = Read(); RG ll ans = 0;    for(RG ll d = 1, j; d <= n; d = j + 1) j = n / (n / d), ans += 1LL * (s[j] - s[d - 1]) * Calc(n / d);    printf("%lld\n", ans);    return 0;}