CodeForces - 1245A Good ol' Numbers Coloring (思维)
Codeforces Round #597 (Div. 2 |
---|
Consider the set of all nonnegative integers: 0,1,2,…. Given two integers a and b (1≤a,b≤104). We paint all the numbers in increasing number first we paint 0, then we paint 1, then 2 and so on.
Each number is painted white or black. We paint a number i according to the following rules:
- if i=0, it is colored white;
- if i≥a and i−a is colored white, i is also colored white;
- if i≥b and i−b is colored white, i is also colored white;
- if i is still not colored white, it is colored black.
In this way, each nonnegative integer gets one of two colors.
For example, if a=3, b=5, then the colors of the numbers (in the order from 0) are: white (0), black (1), black (2), white (3), black (4), white (5), white (6), black (7), white (8), white (9), ...
Note that:
- It is possible that there are infinitely many nonnegative integers colored black. For example, if a=10 and b=10, then only 0,10,20,30 and any other nonnegative integers that end in 0 when written in base 10 are white. The other integers are colored black.
- It is also possible that there are only finitely many nonnegative integers colored black. For example, when a=1 and b=10, then there is no nonnegative integer colored black at all.
Your task is to determine whether or not the number of nonnegative integers colored black is infinite.
If there are infinitely many nonnegative integers colored black, simply print a line containing "Infinite" (without the quotes). Otherwise, print "Finite" (without the quotes).
Input
The first line of input contains a single integer t (1≤t≤100) — the number of test cases in the input. Then t lines follow, each line contains two space-separated integers a and b (1≤a,b≤104).
Output
For each test case, print one line containing either "Infinite" or "Finite" (without the quotes). Output is case-insensitive (i.e. "infinite", "inFiNite" or "finiTE" are all valid answers).
Example
Input
4
10 10
1 10
6 9
7 3
Output
Infinite
Finite
Infinite
Finite
这就是模拟的辗转相减的求最大公约数的算法。最大公约数是1,就能遍历每一个点,即全是白点,不然就全是黑点。
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<vector>
#include<iostream>
using namespace std;
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
int x,y;
cin>>x>>y;
if(__gcd(x,y)==1) puts("Finite");
else puts("Infinite");
}
return 0;
}
最新文章
- Subsonic使用中
- mybatis新增数据后获取自增主键
- 使用Visual Studio Code开发AngularJS应用
- NRF51822之pstorage介绍
- 【转】Android 4.4前后版本读取图库图片和拍照完美解决方案
- ListView的优化
- Roy the Robber
- Git学习02 --暂存区,撤销修改,删除文件
- HH的军训(容斥)
- 使用开源的PullToRefreshScrollView scrollTo和scrollby遇到的问题
- 关于sessionStorage的移动端兼容问题
- Retrofit 2.0 超能实践(四),完成大文件断点下载
- mysql爱之深探测
- Java中构造方法、实例方法、类方法的区别
- No rule to make target &#39;/usr/lib/x86_64-linux-gnu/libproj.so ,needed by &#39;../bin/generate_pointcloud解决方法
- TFS online build change web.config
- 使用Python启动一个简单的服务器
- SpringMVC 数组类型的参数: Cannot generate variable name for non-typed Collection parameter type
- 解决error while loading shared libraries: libXXX.so.X: cannot open shared object file: No such file
- np.array与np.ndarray区别
热门文章
- python通俗讲解闭包
- 【Selenium01篇】python+selenium实现Web自动化:搭建环境,Selenium原理,定位元素以及浏览器常规操作!
- Fiddler实战之使用Fiddler模拟弱网环境(限速)
- 《JavaScript 模式》读书笔记(6)— 代码复用模式2
- webWMS开发过程记录(六)- 详细设计之系统管理
- 今天整理了几个在使用python进行数据分析的常用小技巧、命令。
- Problem D. Ice Cream Tower
- windows批处理protoc生成C++代码
- Linux protobuf
- 微服务统计,分析,图表,监控, 分布式追踪一体化的 HttpReports 在 .Net Core 的应用