Codeforces Round #597 (Div. 2 |
---|
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:
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; }