MB
Хотя что-то я не уверен: возможно наивное "делить пока делится" тоже работает за линию суммарно.
Size: a a a
2020 April 28
f
Нехорошо получается. 3 массива : phi, mp, mp_pow. ВО всех 1e8 элементов, причем тип должен быть не меньше int. 1,5 Гига, ограничение в 1
f
Переслано от Mikail Bagishov
mp_pow[n] = mp[n]
prev := n / mp[n]
if mp[n] == mp[prev] {
mp_pow[n] *= mp_pow[prev]
}
prev := n / mp[n]
if mp[n] == mp[prev] {
mp_pow[n] *= mp_pow[prev]
}
f
Переслано от Mikail Bagishov
Хотя что-то я не уверен: возможно наивное "делить пока делится" тоже работает за линию суммарно.
f
Попробую phi считать в самом конце, но мне кажется из за очистки памяти будет долговато)
K
Все 1e8 чисел будешь раскладывать?
а, нужно все?
K
тогда решето эратосфена, находим первый делитель, делим на него пока делится, phi от того, что осталось, у нас уже вычислено
K
а нужно их именно вычислить или что-то другое?
f
тогда решето эратосфена, находим первый делитель, делим на него пока делится, phi от того, что осталось, у нас уже вычислено
Одного делителя недостаточно, чтобы вычислить phi
Делить пока делится оказалось медленно
Надо вычислить все
Делить пока делится оказалось медленно
Надо вычислить все
f
@MikailBag Задача с Tinkoff если что. Самая обычная, не [Мало памяти], [Мало времени]
MB
@MikailBag Задача с Tinkoff если что. Самая обычная, не [Мало памяти], [Мало времени]
Кажется, я ее тоже не впихал
KK
В чем проблема? Берешь формулу Эйлера с емакса расчет через делители и считаешь
KK
А делители на 10^8 ищутся за корень
f
В чем проблема? Берешь формулу Эйлера с емакса расчет через делители и считаешь
1e12 операций? Неплохо
KK
1e12 операций? Неплохо
Где?
K
Одного делителя недостаточно, чтобы вычислить phi
Делить пока делится оказалось медленно
Надо вычислить все
Делить пока делится оказалось медленно
Надо вычислить все
ты же уже вычислил значения для предыдущих, я правильно понимаю?
KK
1е4*100
f
1е4*100
1e8 чисел, каждое за корень раскладываем