[LuoguP2158][SDOI2008]仪仗队
2024-10-19 00:25:03
[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 ;
}
最新文章
- 纯css3手机页面图标样式代码
- ASP.NET 服务器控件的生命周期
- keil 怎样新建工程,编写代码?
- 用Unity开发HTC VIVE——移动漫游篇
- Centos 如何安装Django环境
- 热门Web开发方式 REST实现原理浅析
- Angularjs简介
- Picasso – Android系统的图片下载和缓存类库
- 解决无法切换到jenkins用户的问题
- CPU Affinity
- [LeetCode] Strange Printer 奇怪的打印机
- canvas霓虹雨
- Oracle创建视图的一个问题
- python3 开发面试题(面向对象)6.6
- /usr/bin/ld: i386:x86-64 architecture of input file `command.o&#39; is incompatible with i386 output
- noip杂题题解
- SDOI2017遗忘的集合
- Xcode 中的IOS工程模板
- Spongebob and Squares---cf599D(数学公式1 + (1+2) + (1+2+3) +....)
- Scrapy Test
热门文章
- win下gosublime配置ctag
- Redis实现分布式锁2
- DOM基础操作(一)
- Drupal网站报错:PDOException: in lock_may_be_available()
- 在小程序中修改上一个页面里data中的数据调用上一个页面的方法
- SQL查询一个表中类别字段中Max()最大值对应的记录
- 我的JS历史知识
- PHPWAMP自启异常,服务器重启后Apache等服务不会自动重启的原因分析
- [EffectiveC++]item12:copy all parts of an object
- [转]unix/linux中的dup()系统调用