Деление-2

Дробь 1/N не имеет периода тогда и только тогда, когда N представимо в виде 2^p*5^q, где p и q – целые неотрицательные числа. Иными словами, данная дробь имеет период тогда и только тогда, когда в числе N существует простой делитель, отличный от 2 и 5. Располагая данным фактом, не сложно решить задачу: для этого следует исключить из числа N все делители 2 и 5, после чего сравнить результат с единицей. Если в результате сравнения получаем равенство, то дробь не имеет периода, в противном случае она периодична.

Докажем утверждения, изложенные выше. Пусть дробь 1/N – не периодична и имеет ровно K цифр после запятой, тогда если ее домножить на 10^K, то мы получим целое число, а именно получим, что значение 10^K/N – целое число, что возможно только в том случае, когда набор простых делителей числителя совпадает с набором простых делителей знаменателя. А поскольку числитель содержит только простые делители 2 и 5, то и знаменатель N имеет тот же набор делителей. И обратно, если N представимо в виде 2^p*5^q, то при K=max(p,q) получаем, что дробь 10^K/N – целое число, что означает конечность дроби 1/N.

Алгоритмическая реализация вышеописанного:

  read(n)
  while(n mod 2=0) n = n div 2
  while*n mod 5=0) n = n div 5
  if(n>1) write('YES') else write('NO')

Следует отметить, что в силу ограничений входных данных в качестве N необходимо выбрать 8-байтовый целый тип (int64 в языке Delphi или __int64 в Visual C++).

[Обсуждение] [Все попытки] [Задача]