408. Однородный генератор

Псевдослучайные числа можно сгенерировать при помощи формулы:

seed(x + 1) = (seed(x) + STEP) % MOD,

где % – операция взятия остатка. Недостаток такого метода получения случайных чисел состоит в том, что циклически будет генерироваться одна и та же последовательность. Например, если STEP = 3 и MOD = 5, то циклически будет повторяться последовательность 0, 3, 1, 4, 2. Если STEP = 15 и MOD = 20, то получим серию чисел 0, 15, 10, 5.

Выяснить, можно при помощи такого генератора получить все числа от 0 до MOD – 1.

Вход. Каждая строка содержит два числа: STEP и MOD (1 £ STEP, MOD £ 100000).

Выход. Для каждого теста вывести значение STEP в колонках от 1 до 10, выровненное справа, значение MOD в колонках от 11 до 20, выровненное справа, и фразу ‘Good Choice‘ или ‘Bad Choice‘, начиная с колонки 25. Если по входным STEP и MOD будут сгенерированы все числа от 0 до MOD – 1, то выводить фразу ‘Good Choice‘. Иначе следует выводить фразу ‘Bad Choice‘. После вывода результата для каждого теста выводить пустую строку.

Пример входа

3 5

15 20

63923 99999

Пример выхода

3 5 Good Choice

15 20 Bad Choice

63923 99999 Good Choice

РЕШЕНИЕ

элементарные вычисления

Анализ алгоритма

Положим seed(0) = 0. Если будут сгенерированы по выше приведенной формуле все числа от 0 до MOD – 1, то seed(i) ¹ 0, i = 1, 2, …, MOD – 1. При этом seed(MOD) = 0. Фразу ‘Bad Choice‘ следует выводить, если существует такое i, 1 £ i £ MOD – 1, что seed(i) = 0.

Реализация алгоритма

Читаем входные значения STEP и MOD. Положим seed = 0. Совершим MOD – 1 итераций генерирования псевдослучайных чисел. Если хотя бы на одном этапе получится seed = 0, то все числа от 0 до MOD – 1 сгенерированы не будут и следует вывести ‘Bad Choice’. Иначе – ‘Good Choice‘.

while(scanf("%d %d",&step,&mod) == 2)

{

seed = 0;

for(i = 0; i < mod - 1; i++)

{

seed = (seed + step) % mod;

if (!seed) break;

}

if (i == mod - 1) printf("%10d%10d Good Choice\n\n",step,mod);

else printf("%10d%10d Bad Choice\n\n",step,mod);

}