文档章节

# codeforces 1245 A. A. Good ol' Numbers Coloring(数学)

o
 osc_7wfxe2gv
发布于 07/14 08:16
字数 478
阅读 19
收藏 0

行业解决方案、产品招募中!想赚钱就来传!>>>

题目大意

给出a,b,按照图中要求染色,问黑色格子是否是有限个(Finite)。

解题思路

这是codeforce官方题解:

在这里插入图片描述

根据染色要求,一个格子如果能表示成\(ax+by(a,b为整数)\)的形式,那么这个格子可以被染成白色。由数学知识可以知道ax+by % gcd(a,b) = 0​,反之任意不能被\(gcd(a,b)\)整除的数都不能表示成\(ax+by\)的形式。

接下来证明,任意一个数\(x^{'}(x^{'}>=a*b)\)能用两个互质的数\((a,b)\)来表示。

构造集合\(S = \{x^{'}, x^{'} - a, x^{'} - 2a, \dots, x^{'} - (b - 1) a\}\),如果集合中任何一个数被染成白色,那么按照染色队则\(x\)也被染成白色。首先\(S\)集合中有b个元素,假设这些元素都不能被\(b\)整除,(一不能整除b的数 对\(b\)的余数只有b-1个,集合中有b个数,对b取余就会产生b种余数)根据鸽巢定理,这个集合中一定存在两个不同的数\(x^{'} - sa, x^{'} - ta \in S (s<t)\)对b取余之后余数一样,那么\((x^{'} - sa) - (x^{'} - ta) = a (t - s)\% b=0\),由于a,b互质,那么\(t-s\)整除\(b\),也就是\(t-s=kb,k>=1\),由于\(x^{'} - sa, x^{'} - ta \in S (s<t)\),可知\(t<b,s<b,(t-s)<b\),所以\(t-s\)整除\(b\)不成立,假设不成立。

也就是集合S中一定存在一个能整除b的数,这个能整除b的数\(x^{'}-sa\)能表示成\(ax+by\)的形式,被染成白色,这个数加上\(sa\)得到\(x^{'}\),也能染成白色。这样就证明了任意一个数\(x^{'}(x^{'}>=a*b)\)能表示成\(ax+by\)的形式。

#include <bits/stdc++.h>
using namespace std;
int t,a,b;
int main(){
    cin>>t;
    while(t--){
        cin>>a>>b;
        if(__gcd(a,b)==1)cout<<"Finite\n";
        else cout<<"Infinite\n";
    }
    return 0;
}
o
粉丝 1
博文 82
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。
TopoJSON

TopoJSON 是 GeoJSON 的扩展,增加了拓扑逻辑的编码。 Rather than representing geometries discretely, geometries in TopoJSON files are stitched together from shared line segments c......

匿名
2012/12/22
3.6K
0
纯Python图形GUI库--PyQtGraph

pyqtgraph 是纯 Python 图形 GUI 库,基于PyQT4 /pyside和NumPy。它主要目的用于在数学/科学/工程中。MIT的开源许可下发布。 主要特点: 基本的2D交互视图中框绘制 线和散点图 数据可平移/缩...

匿名
2013/05/16
9.6K
0
JDK高性能编程之容器

JDK高性能编程之容器 读书笔记内容部分来源书籍深入理解JVM、互联网等,如有错误,请指正,我会及时更正,感谢。 先放一个类图util,点击打开看明细 j360-jdk调试功能 https://github.com/x...

Hi徐敏
2015/10/17
6.7K
18
OpenCASCADE Expression Interpreter by Flex & Bison

OpenCASCADE Expression Interpreter by Flex & Bison eryar@163.com Abstract. OpenCASCADE provide data structure of any expression, relation or function used in mathematics. Flex a......

eryar
2016/05/28
237
0
std::accumulate 的2种用法

accumulate是一种定义在<numeric>头文件里面的一个关于计算范围内元素和的算法。而这个求和的方式有2种:一种是重载,operator +;另外一种是通过二元函数去求和。下面是2种方法的定义: temp...

刘大神
2016/06/30
1K
2

没有更多内容

加载失败,请刷新页面

加载更多

PHP实现RabbitMQ消息队列

先安装PHP对应的RabbitMQ,这里用的是 php_amqp 不同的扩展实现方式会有细微的差异. php扩展地址: http://pecl.php.net/package/amqp 具体以官网为准 http://www.rabbitmq.com/getstarted.htm...

PHP圈子
23分钟前
16
0
pdd笔试题

拼多多提前批的笔试没有报名,但昨天听伙伴们说很难,所以一共4道题,挑了2道会的,自己编了一下。 #include<iostream>#include<vector>#include<algorithm>using namespace std;int ma...

osc_tylqml9v
23分钟前
0
0
拓扑排序算法

/** * 拓扑排序算法,拓扑都是有向无环图 * 使用场景:编译的时候,比如,springboot启动的时候要读取docker系统环境变量,还要读取各配置文件按照顺序 * 还有比如,a的包依赖...

osc_94gn551r
25分钟前
0
0
巨微代理MS1581蓝牙无线收发器

上海巨微MS1581包含8位单片机和低功耗、低成本的BLE收发器,内部集成了发射机、接收机、GFSK调制解调器和BLE基带处理。遵循BLE广播通道通信,具有成本低、体积小、控制方便等优点。巨微代理英...

英尚微电子
25分钟前
12
0
链接测试(内部)

1、长链 https://chelun.eclicks.cn/web/information?info_tid=156984 - 文章test http://cjjl-h5-test.chelun.com/2020/big/index.html - 以小博大test 2、scheme : 钱包 supercoach://myw......

osc_hwc3munb
26分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部