[LuoguP2158][SDOI2008]仪仗队(Link)
现在你有一个\(N \times N\)的矩阵,求你站在\((1,1)\)点能看到的点的总数。
很简洁的题面。
这道题看起来很难,但是稍加分析还是可以看出做法的。
首先我们知道当一个点不能被看到,当且仅当有另外一个点的斜率与它相同且横坐标值小于它。因此假设有两个点\((X1, Y1)(X2, Y2)\)都能被看到,那么一定有\(k_1 ≠ k_2\),那么就是\(\frac{Y1}{X1} ≠ \frac{Y2}{X2}\),那么我们思考可以发现只要\(gcd(X, Y) == 1\)那么就绝对可以看到。那么我们要求的就是横坐标和纵坐标互质的点的个数。那么只要求一下\(\sum_{i= 1}^{N} φ(i)\)然后再加上一个\(1\)就可以了。当然,\(N==1 || 2\)的时候要另当考虑。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;
typedef long long LL ;
const int MAXN = 40010 ;
const int MAXM = 40010 ;
const int Inf = 0x7fffffff ;
int N, E[MAXN] ;
inline int Read() {
int X = 0, F = 1 ; char ch = getchar() ;
while (ch > '9' || ch < '0') F = (ch == '-' ? - 1 : 1), ch = getchar() ;
while (ch >= '0' && ch <= '9') X=(X<<1)+(X<<3)+(ch^48), ch = getchar() ;
return X * F ;
}
inline int Gdb(int X, int Y) {
int Ans = 1 ; while (Ans) {
Ans = X & Y ; X = Y, Y = Ans ;
} return X ;
}
inline void Euler() {
for (int i = 1 ; i <= N ; i ++)
E[i] = i ;
for (int i = 2 ; i <= N ; i ++) {
if (E[i] == i)
for (int j = i ; j <= N ; j += i)
E[j] = E[j] / i * (i - 1) ;
}
}
int main() {
N = Read() ; Euler() ;
if (N == 1){
puts("0") ; return 0 ;
}
if (N == 2) {
puts("2") ; return 0 ;
}
int Ans = 0 ;
for (int i = 1 ; i < N ; i ++)
Ans += E[i] ;
cout << Ans * 2 + 1 << endl ;
return 0 ;
}