@jinxonik / UniLecs #100

VegCut.py

from math import sqrt, log10, ceil
from time import time

MAX_DIGS = 2000

# Рассуждения и описание алгоритма:
# http://telegra.ph/Reshenie-zadachi-ovoshchnaya-narezka-06-07

# Получение списка делителей (включая 1 и n)
def divisors(n):
  lst = [1]
  for i in range(2,int(sqrt(n)+1)):
    if n % i == 0: lst.append(i)
  last = len(lst)-1
  if n//lst[-1] != lst[-1]: lst.append(n//lst[-1])
  for i in range(last-1,-1,-1):
    lst.append(n//lst[i])
  return lst

# Функция Мёбиуса
def Mu(d):
  m, i = 0, 2
  while i*i <= d:
    if d % (i*i) == 0: return 0
    while d % i == 0:
      m += 1
      d //= i
    i += 1
  if d > 1: m += 1
  return 1 if m % 2 == 0 else -1

# Получение числа неприводимых многочленов степени k
def Ik(k):
  I = 0
  for d in divisors(k):
    I += Mu(d)*2**(k//d)
  return I//k

# Определение количества вариантов нарезки
def countVegCut(n):
  if n < 1: return None
  result = 0
  for d in divisors(n):
    result += Ik(d)
  return result

##################################################################

# Возвращает число в виде строки (сокращённой до MAX_DIGS знаков),
# длину исходного числа в цифрах и время _вычисления_
# Если returnString = False, возвращается только время
def countVegCutWithTimer(n, returnString = True):
  timer = time()
  result = countVegCut(n)
  timer = time()-timer
  if not returnString: return (None, None, timer)
  strlen = ceil(log10(result))
  if strlen <= MAX_DIGS:
    string = str(result)
  else:
    # Преобразование в строку очень медленное, так будет быстрее
    string = str(result//10**(strlen-MAX_DIGS//2+2))
    string += '...'+str(result % 10**(MAX_DIGS//2-1))
  return (string, strlen, timer)

# Основной код
nums = (1,2,3,4,5,6,7,12,13,16,30,99,100,256,999)
for n in nums:
  print('%d = %d' % (n, countVegCut(n)))

if input('Show large numbers (y/n)? [y]: ').lower() == 'n': exit(0)

show = True
nums = (9999,10000,25480,99999,100000,543210,
        9999999,10000000,100000007,123456789,1000000007)
for i in range(len(nums)):
  n = nums[i]
  if show and n > 1000000:
    s = input('Hide results for huge numbers (y/n)? [y]: ')
    show = (s.lower() == 'n')
  answer, strlen, timer = countVegCutWithTimer(n, show)
  print()
  if show:
    print('%d = %s' % (n, answer))
    print('%d digits, calculated in %f second(s)' % (strlen, timer))
  else:
    print('Value for %d is calculated in %f second(s)' % (n, timer))
  if i < len(nums)-1:
    if input('Continue (y/n)? [y]: ').lower() == 'n': exit(0)
  else:
    input('Press Enter to quit...');