Part 6.2.3 欧拉函数

P2158 [SDOI2008]仪仗队

很棒的讲解_懂了大概求解

#include<iostream>
#include<cmath>
using namespace std;

int N, ans;

int Phi(int N)
{
    int m = (int)sqrt(N + 0.5), ans = N;
    for (int i = 2; i <= m; ++i)
        if (N % i == 0) {
            ans = ans / i * (i - 1);
            while (N % i)N /= i;
        }
    if (N > 1)
        ans = ans / N * (N - 1);
    return ans;
}

int main()
{
    cin >> N;
    if (N == 1) {
        cout << 0 << endl;
        return 0;
    }
    for (int i = 1; i < N; ++i)
        ans += Phi(i);
    cout << ans * 2 + 1 << endl;
    return 0;
}

//代码转自此博客：https://www.luogu.com.cn/blog/hongzy/solution-p2158
//代码仅用于学习
//该代码虽然简洁，但洛谷却报wrong，因为对题目的一些细节没做好.

right_answer

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>

using namespace std;

typedef long long ll;

map<int, ll> sphi;
bool notprime[5001];
int t, n, prime[5001], top = 0;
ll phi[5001];

inline void pre() {
    phi[1] = 1;
    for (register int i = 2; i <= 5000; ++i) {  
        if (!notprime[i]) prime[++top] = i, phi[i] = i - 1;
        for (register int j = 1; j <= top; ++j) {  
            if (i * prime[j] > 5000) break;  
            notprime[i * prime[j]] = 1;
            if (!(i % prime[j])) {  
                phi[i * prime[j]] = phi[i] * prime[j];
                break;  
            } else phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        } 
    }
    for (register int i = 2; i <= 5000; ++i) phi[i] += phi[i - 1];
}

ll calcphi(int n) {
    if (n <= 5000) return phi[n];
    if (sphi[n]) return sphi[n];
    ll rt = (ll)n * (ll)(n + 1) / 2;
    for (register unsigned int l = 2, r; l <= n; l = r + 1) {
        r = n / (n / l);
        rt -= (r - l + 1) * calcphi(n / l);
    }
    return sphi[n] = rt;
}

int main() {
    scanf("%d", &n); pre();
    if (n == 1) printf("0");
    else printf("%lld", 2 * calcphi(n - 1) + 1); 
    return 0;
}

//代码转自此博客：https://smallbasic.blog.luogu.org/solution-p2158
//代码仅用于学习