P2158 [SDOI2008] 仪仗队:

一开始还确实没来思路，但是昨晚看了一个水题也是用到了斜率，所以就想到了斜率。

很明显斜率相同的会被遮挡，也就是说不是最简分数的形式就会被遮挡。

很显然求一下互质的坐标数就行。

这里的话左下角那个人是不算的，然后我们要以左下角为(0,0)点来看才对。

// Author: levil
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> pii;
const int N = 4e4 + 5;
const int M = 2e4 + 5;
const double eps = 1e-10;
const LL Mod = 1e9 + 7;
#define pi acos(-1)
#define INF 1e9
#define dbg(ax) cout << "now this num is " << ax << endl;
inline int read() {
    int f = 1;int x = 0;char c = getchar();
    while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
    while(c >= '0' && c <= '9'){x = (x<<1)+(x<<3)+(c^48);c = getchar();}
    return x*f;
}
inline long long ADD(long long x,long long y) {return (x + y) % Mod;}
inline long long DEC(long long x,long long y) {return (x - y + Mod) % Mod;}
inline long long MUL(long long x,long long y) {return x * y % Mod;}

bool vis[N];
int prime[N],tot = 0,phi[N];
void init() {
    for(int i = 2;i < N;++i) {
        if(!vis[i]) {
            prime[++tot] = i;
            phi[i] = i - 1;
        }
        for(int j = 1;j <= tot && prime[j] * i < N;++j) {
            vis[prime[j] * i] = 1;
            if(i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            else phi[i * prime[j]] = phi[i] * phi[prime[j]];
        }
    }
}
void solve() {
    init();
    int n;n = read();
    if(n == 1) printf("0\n");
    else {
        LL ans = 1LL * (n - 1) * (n - 1) + 3;
        for(int i = 2;i < n;++i) {
            ans -= (i - phi[i] - 1) * 2 + 1;
        }
        printf("%lld\n",ans - 1);
    }

}
int main() {
    solve();
    system("pause");
    return 0;
}

View Code