https://ac.nowcoder.com/acm/problem/20313——仪仗队(欧拉函数)

题目：https://ac.nowcoder.com/acm/problem/20313
思路：能看到的士兵的横纵左坐标必然是互质的，取左上三角形，得出结果为ans，最终结果就是2*ans+1.而ans就是每一行的结果之和，每一行的结果就是欧拉函数。
代码：

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<vector>
#include<set>
#include<utility>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const LL mod=1e9+7;
int read() {
    char ch=getchar();int x=0,f=1;
    while(ch<'0' || ch>'9')    {if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int gcd_(int a,int b) {return b==0?a:gcd_(b,a%b);}
LL fpow(LL a,LL b) {
    LL res=1;
    while(b) {
        if(b&1) res=(res*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return res;
}
LL euler(LL n) {
    LL ans=n;
    for(LL i=2;i*i<=n;++i) {
        if(n%i==0) {
            ans=ans/i*(i-1);
            while(n%i==0) n/=i;
        }
    }
    if(n>1) ans=ans/n*(n-1);
    return ans;
}
int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
//    cout<<"Accepted!\n";
    LL n;
    cin>>n;
    LL ans=0;
    for(LL i=1;i<n;++i) ans+=euler(i);
    cout<<ans*2+1; 
    return 0;
}