Задача на 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%)
for i in range((int(input())))
. В условии на сайте ничего не написано, про то, что что-то будет вводиться через input.