[SDOI2008]仪仗队

实际上就是求Gcd(i - 1, j - 1) == 1 的 (i, j) i >= 2, j >= 2 的个数加2
i - 1 和 j - 1 互质 那不就是sigma phi(i - 1)
最后答案*2+1即可

# include <stdio.h>
# include <stdlib.h>
# include <iostream>
# include <algorithm>
# include <string.h>
# define IL inline
# define RG register
# define Fill(a, b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;

IL ll Read(){
    RG char c = getchar(); RG ll x = 0, z = 1;
    for(; c < '0' || c > '9'; c = getchar()) z = c == '-' ? -1 : 1;
    for(; c >= '0' && c <= '9'; c = getchar()) x = (x << 1) + (x << 3) + c - '0';
    return x * z;
}

int n, ans;
//Gcd(i - 1, j - 1) == 1
//sigma phi(i - 1)
IL int Phi(RG int x){
    RG int cnt = x;
    for(RG int i = 2; i <= x; i++){
        if(x % i) continue;
        while(!(x % i)) x /= i;
        cnt = cnt - cnt / i;
    }
    if(x > 1) cnt = cnt - cnt / x;
    return cnt;
}

int main(RG int argc, RG char* argv[]){
    n = Read();
    for(RG int i = 2; i <= n; i++) ans += Phi(i - 1);
    printf("%d
", ans * 2 + 1);
    return 0;
}