Решение задачи "Старая добрая раскраска чисел" с Codeforces

Без пояснения   Просмотров: 16


Рассмотрим множество всех неотрицательных целых чисел : 0,1,2,…. Даны два целых числа a и b (1≤a,b≤104). Мы раскрашиваем все числа в порядке возрастания: сначала раскрашиваем 0, затем раскрашиваем 1, затем раскрашиваем 2 и так далее.

Каждое число будет раскрашено в белый или черный цвет. Очередное число i раскрашивается по следующим правилам:

если i=0, то раскрашено в белый цвет;
если i≥a и i−a раскрашен в белый цвет, то и i раскрашен в белый цвет;
если i≥b и i−b раскрашен в белый цвет, то и i раскрашен в белый цвет;
если i не раскрашен в белый цвет, то раскрашен в черный.
Таким образом, каждое неотрицательное целое число будет раскрашено в один из двух цветов.

Например, если a=3, b=5, то цвета чисел (в порядке от 0 и далее) будут равны: белый (0), черный (1), черный (2), белый (3), черный (4), белый (5), белый (6), черный (7), белый (8), белый (9), ...

Обратите внимание, что:

Возможно, что существует бесконечно много неотрицательных целых чисел, раскрашенных в черный. Например, если a=10 и b=10, тогда только 0,10,20,30 и любые другие неотрицательные целые числа, десятичная запись которых заканчивается на 0 — белые. Все остальные — черные.
Также возможно, что существует только конечно много неотрицательных целых чисел, раскрашенных в черный. Например, если a=1 и b=10, тогда ни одно число не покрашено в черный цвет.
Ваша задача — определить, конечно ли количество чисел, которые раскрашены в черный цвет, или бесконечно.

Если существует бесконечно много чисел, раскрашенных в черный, то выведите единственную строку, содержащую «Infinite» (без кавычек). Иначе выведите «Finite» (без кавычек).

Код

#include <bits/stdc++.h>

using namespace std;

int t;
int a, b; 

int main()
{
	cin >> t;
	while (t--) {
		cin >> a >> b;
		if (__gcd(a, b) != 1)
			cout << "Infinite\n";
		else
			cout << "Finite\n";
	}

	return 0;
}

         

 Администратор Photo Автор: Администратор


Отправить решение задачи
Чтобы отправить решение вам нужно войти в систему или зарегистрироваться

Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться