[SDOI2008]仪仗队

思路：

:回归梦想

#include<bits stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+5;
int prime[maxn], vis[maxn],phi[maxn];
void initial(const int n=1e5) {
    int cnt=0; phi[1]=1;
    for(int i=2;i<=n;i++) {
        if(vis[i]==0) { prime[++cnt]=i; phi[i]=i-1;vis[i]=i; }
        for(int j=1;j<=cnt;j++) {
            if(prime[j]>vis[i]||i*prime[j]>n) break;
            vis[i*prime[j]]=prime[j];
            if(i%prime[j]==0) {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
    for(int i=1;i<=n;i++) phi[i]+=phi[i-1];
}
int main() {
    initial();
    int n; scanf("%d",&n);
    printf("%lld\n",2ll*phi[n-1]+1);
    return 0;
}

#include <bits stdc++.h>
using namespace std;
const int maxn = 5e4+10;
int n, phi[maxn];
void get_phi(int n) {
    phi[1] = 1;
    for(int i = 2; i <= n; i++) if(!phi[i]) {
        for(int j = i; j <= n; j += i) {
            if(!phi[j]) phi[j] = j;
            phi[j] = phi[j] / i * (i-1);
        }
    }
}
int main() {
    scanf("%d", &n);
    get_phi(n);
    int ans = 0;
    for(int i = 1; i < n; i++) ans += phi[i];
    printf("%d", ans * 2 + 1);
    return 0;
}

#include <bits stdc++.h>
using namespace std;
const int maxn = 5e4+10;
int n, phi[maxn];
long long Euler( long long n ){
       long long res = n;
     for( long long i =2 ;i*i<=n;i++){
         if( n %i == 0 ){
            n/=i;
            res = res - res/i;
        }
         while( n % i==0)
         n/=i;
     }
     if( n > 1 )
         res = res - res/n;
     return res;
}

int main() {
    scanf("%d", &n);
    int ans = 0;
    for(int i = 1; i < n; i++) ans += Euler(i);
    printf("%d", ans * 2 + 1);
    return 0;
}

也可以先筛出素数再用公式法：

vector<int>prime;
bool vis[maxm];
void initial() {
    for (int i = 2; i < maxm ; ++i) {
        if (!vis[i]) prime.emplace_back(i);
        for (int j = 0,size=prime.size(); j < size; ++j) {
            if (i * prime[j] >= maxm) break;
            vis[i * prime[j]] = true;
            if (i % prime[j] == 0) break;
        }
    }
}
inline ll Phi(ll p){
    ll x=p;
    for(int i:prime) {
        if(i>x) break;
        if(x%i==0){
            while(x%i==0)x/=i;
            p=p/i*(i-1);
        }
    }
    if(x>1)p=p/x*(x-1);
    return p;
}