0

Задача на acmp.ru "Осколки"

На Землю надвигается страшная угроза, к нам летит облако из N огромных астероидов. Известно только то, что все они одинакового размера. У учёных есть ракеты, способные уничтожить астероиды, каждая такая ракета характеризуется зарядом m – натуральным числом от 1 до N. Но, к сожалению, неизвестно, как каждая из ракет поведёт себя при столкновении с астероидом, поэтому было принято решение запустить по одной ракете каждого вида. И только после столкновения стало известно, что ракета с зарядом m после уничтожения астероида образует осколки в количестве, равном наибольшему общему делителю чисел m и N. Помогите узнать, сколько осколков упадёт на Землю, у Вас совсем мало времени!

Входные данные

В единственной строке входного файла INPUT.TXT содержится натуральное число N – количество запущенных ракет и взорванных ими астероидов (1 ≤ N ≤ 10^18).

Выходные данные

В выходной файл OUTPUT.TXT выведите количество осколков, которые упадут на Землю.

Не проходит 8й тест из-за превышения времени(2,203 с.)

# -*-coding: cp866 -*- 
s=0;
def gcd(a, b): 
    while b: a, b = b, a % b 
    return a 
try:
  f = open("input.txt",'r')
  n = int(f.readline())
  f.close
except IOError: print ("No file") 
for i in range((int(input()))): s+=gcd(i,n);
print("s=",str(s));
with open("output.txt", 'w') as f1: f1.write(str(s)); 
f1.close;

Ошибка "Time limit exeeded" (Время: 2 сек. Память: 16 Мб Сложность: 88%)

9
  • 1
    Текст задачи - в вопрос. И вопрос должен быть развернутым.
    – strawdog
    19 мая 2021 в 5:27
  • вот бы кто догадался давать переменным в коде такие же имена, как в задаче, чтобы другие не гадали, где тут что. 19 мая 2021 в 5:41
  • В описании задачи не вижу, чтобы где-то было про ввод через input - там точно что-то вводится?
    – insolor
    19 мая 2021 в 6:08
  • @insolor Я делал через файл, и можете посмотреть на самом сайте условие.
    – Roman
    19 мая 2021 в 6:22
  • @Roman у вас есть в коде чтение из файла, но значение для range считывается через input: for i in range((int(input()))). В условии на сайте ничего не написано, про то, что что-то будет вводиться через input.
    – insolor
    19 мая 2021 в 6:28

1 ответ 1

2

Задача довольно сложная.

Данная сумма эквивалентна

Sum{по всем d: делителям n} (d * Fi(n/d))

Где Fi() - функция Эйлера

Таким образом, потребуется выполнить факторизацию n на простые множители.
Для вычисления функции Эйлера потребуется факторизация n/d - а она уже фактически есть как разность факторизаций n и d


Нагуглил более простой способ, основанный на той же функции Эйлера под капотом.

Опять же выполняем факторизацию на простые в виде (ai - степени простых)

n = p1^a1 * p2^a2 *....pk^ak    

И тогда результат

SumOfGCD = Prod[i=1..k} ((ai+1)*pi^ai - ai*pi^(ai-1))

Пример

n = 9876543212345678
fac = factors(n)
print(fac)
res = 1
for x in fac:
    res *= x[0]**(x[1] - 1) * (x[1] * x[0] + x[0] - x[1])
print(res)

[(2, 1), (11, 1), (73, 1), (101, 1), (137, 1), (709, 1), (626861, 1)]
890508372065319735

n=2276680122000
[(2, 4), (3, 8), (5, 3), (173501, 1)]
294146224081200

n=6
[(2, 1), (3, 1)]
15
2
  • Я немного не понял, можете добавить это в код?
    – Roman
    19 мая 2021 в 6:24
  • Если у вас проблемы "с кодом", с реализацией несложных формул, то зачем берётесь за задачи, требующие неплохого владения теорией чисел (сложность 88%, надо полагать, довольно высока)?
    – MBo
    19 мая 2021 в 7:02

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.