luoguP2735 电网 Electric Fences
2024-09-27 14:42:34
一道校内模拟赛遇见的题
** 不会正解就真的很麻烦的 数学题 **
有一种东西叫 皮克定理
发现的千古神犇:
姓名:George Alexander Pick(所以叫皮克定理呀
国籍:奥地利(蛤!竟然不是匈牙利。。。逃。。。
皮克定理是干蛤的
就是在一张网格纸上(对,就是网格纸,关于SPFA,他,死了),上面画着纵横两组平行线,相邻平行线之间的距离都相等,这样两组平行线的交点,就是所谓格点。如果取一个格点做原点O,取通过这个格点的横向和纵向两直线分别做X轴和Y轴,并取原来方格边长做单位长,建立一个坐标系。这时前面所说的格点,显然就是纵横两坐标都是整数的那些点。由于这个缘故,我们又叫格点为整点。
一个多边形的顶点如果全是格点,这多边形就叫做格点多边形。有趣的是,这种格点多边形的面积计算起来很方便,只要数一下图形边线上的点的数目及图内的点的数目,就可用公式算出。
公式是啥?
公式:2S = 2a + b - 2
其中a表示多边形内部的点数,b表示多边形边界上的点数,S表示多边形的面积。
证明,不存在的。。。(光速逃离。。。
题解:
这题显然求的是a,2S可用m*p来求,b则用gcd来。
所以,反向套公式就完事了。。。
CODE:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#define ll long long
using namespace std;
inline ll gcd(ll x,ll y) {
return x % y == 0 ? y : gcd(y,x % y);
}
ll n,m,p;
int main() {
//freopen("fence.in","r",stdin);
//freopen("fence.out","w",stdout);
scanf("%lld%lld%lld",&n,&m,&p);
ll s = p * m / 2;
ll cnt = (gcd(n,m) + gcd(abs(n - p),m) + p) / 2;
ll ans = s - cnt + 1;
printf("%lld\n",ans);
return 0;
}
最新文章
- Shell教程
- winform 用户控件、 动态创建添加控件、timer控件、控件联动
- NSRunLoop
- 用canvas生成二维码
- PetaPoco - 轻量级高性能的ORM框架(支持.NET Core)
- 核心思想:百度网盘怎么盈利(互联网的高速更新决定了:亏钱你还有点机会,放弃连门都进不了),战略预备队 good
- LXC-Linux Containers介绍
- 手工构建ISO的基本步骤
- MAC 下cocos2d-x lua 使用dragonbones的方法
- 【HTML5游戏开发小技巧】RPG情景对话中,令文本逐字输出
- Mac 10.10 下安装jdk 1.7 以上
- nodejs抓取数据二(列表解析)
- CSS之浏览器默认样式设置
- 关于移动APP与Web APP的测试重点以及区别
- spring boot整合redis
- 使用supervisor管理进程
- Windows Server 2016-DHCP服务器审核日志大小调整
- React.createClass和extends Component的区别
- 函数的作用域、global与nonlocal
- 【sql小坑】在group by里用select字段的别名?
热门文章
- 导入eclipse工程到Android Studio中
- Android中用GridView实现九宫格的两种方法(转)
- 【bzoj3926】【Zjoi2015】诸神眷顾的幻想乡
- 解决“mongoengine.fields.ImproperlyConfigured: PIL library was not found”报错
- laravel 命令行输出进度条
- hdu 6311 欧拉回路
- Java基础-IO流对象之数据流(DataOutputStream与DataInputStream)
- 【转载】C#, VB.NET如何将Excel转换为PDF
- windows查找端口占用/ 终结端口占用 ------------windows小技巧
- NOIP2016 组合数问题