108
107-ая задача - я даже не помню ее номер, что-то про произведение простых множителей - оказалось простой до неприличия. Решето Эратосфена опять решило.
108-ая задача (104) оказалась забавной.
Вначале попробовал решать влоб - но это оказалось слишком долго. Потом подумав, придумалась такая оптимизация - вначале поискать все числа, младшие 9 цифр которых удовлетворяют необходимому условию. Это сделать просто, потому как нам не надо старшие разряды и скорость поиска таких цифр очень большая. Дальше оставалось только проверить номера таких "младших" чисел на соблюдение условия для старших девяти цифр. Для этого надо было научиться быстро считать фисла фибоначи по его номеру. Побродив по нету, нашел вот такие рекурсивные формулы:
F(2*n)=F(n)*(2*F(n-1) + F(n))
F(2*n-1)=F(n-1)^2+F(n)^2
Ну а дальше дело техники.
Еще одна задача и я стану 10-ым в республике.
108-ая задача (104) оказалась забавной.
Вначале попробовал решать влоб - но это оказалось слишком долго. Потом подумав, придумалась такая оптимизация - вначале поискать все числа, младшие 9 цифр которых удовлетворяют необходимому условию. Это сделать просто, потому как нам не надо старшие разряды и скорость поиска таких цифр очень большая. Дальше оставалось только проверить номера таких "младших" чисел на соблюдение условия для старших девяти цифр. Для этого надо было научиться быстро считать фисла фибоначи по его номеру. Побродив по нету, нашел вот такие рекурсивные формулы:
F(2*n)=F(n)*(2*F(n-1) + F(n))
F(2*n-1)=F(n-1)^2+F(n)^2
Ну а дальше дело техники.
Еще одна задача и я стану 10-ым в республике.