Time limit exeeded

Question

Задача на 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%)

Answer 1

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

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

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

БЛОГ НА HUSL

Time limit exeeded

Ответы (1 шт):